Anna University Local Contest #10

For the Australian Open preparation, Stan Wawrinka is planning to move into a new practice court in Melbourne. For that, he should transfer all his tennis balls from the old court to the new one. He divides all his balls into a number of group(s) and will put each group of balls into a different bag. Stan is very sentimental(remember his pink-checkered shorts in French Open). So, he wants to make sure that the number of balls in each bag is not a prime number as he doesn't like prime numbers. He has bags which can accommodate any arbitrary number of balls. Please help him find the minimum number of bags which he needs to transfer all the balls.

Input

First line consists of number of test cases - T.

For each test case, there will be a single integer N denoting the number of balls.

Output

For each test case, print a single integer denoting the minimum number of bags. If it's not possible to divide the number as required, print -1.

Constraints:

1<=T<=100

1<=N<=10^12

Example

Input:
2
17
16

Output:
2
1

Explanation

In the first test case, 17 can be split into 2 groups in various ways one of which is (8,9).

In the second test case, 16 is not a prime and so he can put all the balls in the same bag.