Obeleži sve kategorije koje odgovaraju problemu

Mala Kaćolina je odavno svima nama poznata kao odličan matematičar. Kako je lako uspela da pomnoži sve moguće parove brojeva manjih od milijardu, rešila je da sebi malo oteža igru sa brojevima.

Definisaćemo trivijalnost broja $x$ kao količnik zbira njegovih pozitivnih delilaca i njega samog (na primer trivijalnost broja $6$ iznosi $\frac{1 + 2 + 3 + 6}{6} = 2$).

Za broj $x$ kažemo da je najtrivijalniji broj u intervalu $[l,r]$ (skupu brojeva $\{ l, l+1, \ldots, r-1, r \}$), ako pripada datom intervalu i njegova trivijalnost je najmanja od trivijalnosti svih brojeva na tom intervalu i ne postoji nijedan drugi broj manji od njega koji pripada intervalu i ima istu trivijalnost.

Kaćolina je sebi zadala $T$ pitanja oblika :

• Naći najtrivijalniji broj u intervalu $[2, A_i]$

Da li možete odgovoriti na ove upite brže od Kaćoline (njoj otprilike treba dve sekunde da odgovori na sva pitanja)?

Opis ulaza

Prva linija standardnog ulaza sadrži jedan prirodan broj $T$, koji predstavlja broj pitanja koje je Kaćolina zadala. Svaka od narednih $T$ linija sadrži jedan broj, tačnije $i$-ta linija sadrži broj $A_i$.

Opis izlaza

Za svaki od zadatih $T$ upita ispisati najtrivijalniji broj u zadatom intervalu, tačnije u $i$-toj liniji ispisati najtrivijalni broj u intervalu [$2$, $A_i$].

Primer

Ulaz

1
4

Izlaz

3

Objašnjenje primera

Dat je samo jedan upit i potrebno je naći najtrivijalniji broj u intervalu $[2, 4]$.

Trivijalnost broja 2 : $\frac{1 + 2}{2} = 1.50$

Trivijalnost broja 3 : $\frac{1 + 3}{3} = 1.33$

Trivijalnost broja 4 : $\frac{1+2+4}{4} = 1.75$

Najmanju trivijalnost ima broj $3$, tako da je on rešenje ovog primera.

Ograničenja

• $1 \leq T \leq 10$
• $2 \leq A_i \leq 5 \cdot 10^6$

Podzadaci

• U test primerima vrednim $10$ poena važi ograničenje $2\leq A_i \leq 20$
• U test primerima vrednim $20$ poena važi ograničenje $2\leq A_i \leq 1000$
• U test primerima vrednim $30$ poena važi ograničenje $2\leq A_i \leq 2\cdot 10^5$
• U test primerima vrednim $40$ poena nema dodatnih ograničenja.