Бағдарламалауда \(f(a)\) функциясы кеңінен белгілі, ол кез келген бүтін сан \(a > 1\) үшін оның 1-ден үлкен ең кіші бөлгішін қайтарады.

Бұл функцияның бар екені туралы білген соң, Aldk досы Daki_sa-ның білімін тексергісі келді. Оған \(f(x)\) табуды сұраудың орнына, бұл тым оңай болар еді, ол қиынырақ тапсырма ұсынды — \(f(x^2 - 1)\) табу.

Daki_sa-ға бұл тапсырманы шешуге көмектесіңіз.

Енгізу

Бірінші жолда бүтін сан \(t\) \((1 \le t \le 100)\) берілген — кіріс деректерінің саны.

Әрбір деректер жиынтығының жалғыз жолында бүтін сан \(x\) \((2 \le x \le 10^9)\) берілген.

Шығару

Әрбір деректер жиынтығы үшін \(f(x^2 - 1)\) мәнін шығарыңыз.

Мысалдар

Енгізу 1

3
2
3
36

Жауап 1

3
2
5

Ескертпелер

Алғашқы деректер жиынтығында \(2^2-1 = 3\)-тің бөлгіштері: \(1\), \(3\). Олардың ішіндегі ең кіші (\(1\)-ден үлкен) бөлгіш — \(3\).

Екінші деректер жиынтығында \(3^2-1 = 8\)-дің бөлгіштері: \(1\), \(2\), \(4\), \(8\). Олардың ішіндегі ең кіші (\(1\)-ден үлкен) бөлгіш — \(2\).