Alice is very fond of prime numbers. Given a number she wants to determine whether it is prime or not.

Input

First line of input contains number of test cases t. t lines follow. Each line contains a positive integer N. The largest integer given in the input file has 30 digits.

Output

For each test case output a single integer. If the number is not prime output -1 otherwise output 1.

Constraints

1<=t<=100

1<=N<=10^30-1