A Number Game

Moderate

0/80

Contributed by

0 upvote

Problem statement

Ninja has an integer 'A'.

He will go through all integers 'X' from 1 to 10^18 and for every 'X', he will store the value of 'LCM(X,A) ÷ X'.

He wants to know the number of unique values he will obtain in the end.

Example :

‘A’ = '2'
For X = 1, Ninja will get LCM(1,2) ÷ 1 = 2/1 = 2.
For X = 2, Ninja will get LCM (2,2) ÷ 2 = 2/2 = 1.
For X = 3, Ninja will get LCM (3,2) ÷ 3  = 6/3 = 2.
For X = 4, Ninja will get LCM (4,2) ÷ 4 = 4/2 = 2.
For X = 5, Ninja will get LCM (5,2) ÷ 5 = 10/2 = 2.
For X = 6, Ninja will get LCM (6,2) ÷ 6 = 6/6 = 1.
And so on, It can be verified that Ninja will never get any integer other than 1 and 2. Hence the answer for 'A' = 2 is 2.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an integer 'T', which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains a single integer 'A'.

Output format :

For each test case, output the number of unique integers obtained for the function provided in the problem statement.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 ≤ T ≤ 10 
0 ≤ A ≤ 10^10

Time Limit: 1 sec

Sample Input 1 :

2
1
3

Sample Output 1 :

1
2

Explanation Of Sample Input 1 :

For 'A' =1, the LCM of '(X,1)' (1 <=X <= 10^18) is always X. Hence, we will always obtain the same integer (X/X) = 1.

For 'A' = 3,
For X = 1, Ninja will get LCM(1,3) ÷ 1 = 3/1 = 3.
For X = 2, Ninja will get LCM (2,3) ÷ 2 = 6/2 = 3.
For X = 3, Ninja will get LCM (3,3) ÷ 3  = 3/3 = 1.
For X = 4, Ninja will get LCM (4,3) ÷ 4 =  12/4 = 3.
For X = 5, Ninja will get LCM (5,3) ÷ 5 = 15/5 = 3.
For X = 6, Ninja will get LCM (6,3) ÷ 6 = 6/6 = 1.
And so on, It can be verified that Ninja will never get any integer other than 1 and 3. Hence the answer for 'A' = 3 is 2.

Sample Input 2 :

2
171
172

Sample Output 2 :

6
6

Console