Weird GCD Value solution codechef
You are given two positive integersand , we define as the maximum value of where is some natural number. Formally,
, whererepresents the set of natural numbers and represents the greatest common divisor of and .
You are given an integer. You need to find the number of ordered pairs (where are positive) such that .
Note that pairsand are considered different if . For example, pair is not the same as .
- The first line of the input contains a single integer denoting the number of test cases. The description of test cases follows.
- The first and only line of each testcase contains a single integer .
Weird GCD Value solution codechef Output Format
For each testcase, output the number of ordered pairssuch that .
Weird GCD Value solution codechef Sample Input 1
2 1 3
Sample Output 1
Explanation Weird GCD Value solution codechef
Test case: For , we see that . Therefore the answer is . It can be verified that there are no other pairs for which the value is .
Test case: For , there exists ordered pairs for which the value is . One of them is .