SPOJ in Armenian

Բայթլանդիայի կառավարությունը հարկերը գանձում է տարօրինակ ձևով. եթե Դուք ունեք n (n>1) դոլար եկամուտ, ապա պարտավոր եք վճարել m դոլար հարկ, որտեղ m-ը n-ի ամենամեծ բաժանարարն է (չհաշված n-ը): Օրինակ՝ եթե Դուք վաստակել եք 6 դոլար, ապա պարտավոր եք վճարել 3 դոլար, իսկ եթե ունեք 25 դոլար, ապա պարտավոր եք վճարել 5-ը: Դուք վաստակել եք N դոլար, և չեք ուզում շատ հարկ վճարել: Դրա համար անհրաժեշտ է Ձեր ունեցած գումարը բաժանել մի քանի մասի այնպես, որ գումարային հարկը լինի մինիմալ:

Մուտք

Առաջին տողում T (1<=T<=100): Հաջորդ T տողերում - միակ N (2 ≤ N ≤ 109) թիվ - Ձեր ստացած եկամուտը:

Ելք

T տողեր, ամեն տողում միակ թիվ՝ խնդրի պատասխանը. այն մինիմալ հարկը, որ ստիպված եք վճարել:

Օրինակներ

Մուտք.

2

4

27

Ելք.

2

3