For two positive integers a and b, let g(a, b) = [gcd]
(a, b) + lcm.

For a positive integer N, let f(N) denote the minimum value of g(a, b) over all the pairs of positive integers (a, b) such that a+b = N.

Find out the number of ordered pairs (a, b) such that a+b = N and g(a, b) = f(N).

------ Input Format ------

• The first line of input will contain an integer T — the number of test cases. The description of T test cases follows.
• The first and only line of each test case contains a positive integer N.

------ Output Format ------

For each test case, output the number of ordered pairs (a, b) such that a+b = N and g(a, b) = f(N).

------ Constraints ------

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 10^{9}$

----- Sample Input 1 ------
2
4
105
----- Sample Output 1 ------
3
14

----- explanation 1 ------
Test case $1$:
- For the pair $(1, 3)$, $g(1, 3) = gcd(1,3)+lcm(1,3)=1+3=4$.
- For the pair $(2, 2)$, $g(2, 2) = gcd(2,2)+lcm(2,2)=2+2=4$.
- For the pair $(3, 1)$, $g(3, 1) = gcd(3,1)+lcm(3,1)=1+3=4$.

Hence, $f(4) = 4$. There are three pairs $(a, b)$ satisfying $a+b = N$ and $g(a, b) = f(N)$.

见题面

见题面