E2 - Rozklad na súčet

Je dané číslo X. Toto číslo by sme chceli zapísať ako súčet niekoľkých (aspoň dvoch) za sebou idúcich prirodzených čísel. Vašou úlohou je zistiť, aký najmenší počet sčítancov na to musíme použiť.

Vstup

Prvý riadok vstupu obsahuje kladné celé číslo N určujúce počet testovacích sád (1 ≤ N ≤ 100). Každý z nasledujúcich N riadkov obsahuje jedno kladné celé číslo X.

Výstup

Pre každé X zo vstupu vypíšte jedno kladné celé číslo k (k ≥ 2) – najmenší možný počet sčítancov, ktoré musíme použiť. V prípade, že číslo X sa nedá rozložiť na súčet aspoň dvoch za sebou idúcich prirodzených čísel, vypíšte 0.

E1

1 ≤ X ≤ 1 000 000

E2

1 ≤ X ≤ 2⁶³−1

Príklad

Vstup:

4
4
10
42
47

Výstup:

0
4
3
2