Spoj Peru

Una pandilla de K conejitos han asaltado un mercado y robaron N zanahorias.
En ese momento un zorro que corria por ahi se ofrecio a dividir las zanahorias equitativamente entre los conejitos con la condicion de obtener el resto (menos de K zanahorias) como pago por sus servicios.

Mientras que el Zorro pensaba como dividir las zanahorias un conejito se infiltro en la pandilla y obtuvo la misma cantidad de zanahorias que los demas.
Sucede algo curioso los conejitos hubiesen obtenido la misma cantidad de zanahorias aun si no estuviese el infiltrado.

Encuentre la minima cantidad de conejitos para que esto pueda suceder.

Input

La primera linea contiene el numero de casos de prueba t, 1<=t<=100000, en cada una de las t lineas siguientes obtendras un entero N para el correspondiente caso, 1<=N<=10¹⁸

Output

Para cada caso, imprime en cada linea el minimo posible del numero de conejitos en la pandilla.

Example

Input:
4
2
9
11
18

Output:
3
5
4
5