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 mutiple 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