Given an integer n.

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

1 <= c <= 10^5

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^9

Output

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

Example

Input:
3
6
9
10

Output:
3
2
2