Project Euler #135: Same differences

_{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