Given an integer n.

Find how many integers c are there such that their Pisano period is a factor of n.

1 ≤ c ≤ 10⁵

There are multiple test cases.

Input

The first line contains number of test cases, 1 ≤ t ≤ 100

Next t lines contain an integer n each. 1 ≤ n ≤ 10⁹

Output

Output the answer to each test case on a separate line.

Example

Input:
3
6
9
10

Output:
3
2
2