This problem is a programming version of Problem 135 from projecteuler.net
Given the positive integers, , , and , are consecutive terms of an arithmetic progression, the least value of the positive integer, , for which the equation, , has exactly two solutions is :
It turns out that is the least value which has exactly solutions.
Let be the number of solutions for this value of . For example, and .
Given , what is ?
Input Format
The first line of input contains , the number of test cases.
Each test case consists of one line containing a single integer, .
Constraints
In the first 10 test cases (worth 50% of the total points):
In the next 5 test cases (worth 50% of the total points):
Output Format
For each test case, output one line containing a single integer, the answer for that test case ().
Sample Input
2
27
1155
Sample Output
2
10