Weird GCD Value

 You are given two positive integers 

a$a$ and b$b$, we define f(a,b)$f(a,b)$ as the maximum value of |gcd(a,x)−gcd(b,x)|$|gcd(a,x)-gcd(b,x)|$ where x$x$ is some natural number. Formally,

f(a,b)=maxx∈N|gcd(a,x)−gcd(b,x)|$f(a,b)=\underset{x\in \mathbb{N}}{max}|gcd(a,x)-gcd(b,x)|$

, where N$\mathbb{N}$ represents the set of natural numbers and gcd(a,b)$gcd(a,b)$ represents the greatest common divisor of a$a$ and b$b$.

You are given an integer k$k$. You need to find the number of ordered pairs (a,b)$(a,b)$ (where a,b$a,b$ are positive) such that f(a,b)=k$f(a,b)=k$.

Note that pairs (a,b)$(a,b)$ and (b,a)$(b,a)$ are considered different if a≠b$a\ne b$. For example, pair (1,2)$(1,2)$ is not the same as (2,1)$(2,1)$.

Input Format

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first and only line of each testcase contains a single integer k$k$.

Output Format

For each testcase, output the number of ordered pairs (a,b)$(a,b)$ such that f(a,b)=k$f(a,b)=k$.

Constraints

• 1≤T≤106$1\le T\le {10}^6$
• 1≤k≤106$1\le k\le {10}^6$

Sample Input 1 

2
1
3

Sample Output 1 

2
6

Explanation

Test case 1$1$: For k=1$k=1$, we see that f(1,2)=f(2,1)=1$f(1,2)=f(2,1)=1$. Therefore the answer is 2$2$. It can be verified that there are no other pairs for which the f$f$ value is 1$1$.

Test case 2$2$: For k=3$k=3$, there exists 6$6$ ordered pairs for which the f$f$ value is 3$3$. One of them is (4,3)$(4,3)$.

• Tweet
• Share
• Share
• Share
• Share

Related Post