Count a * b
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 173 Accepted Submission(s): 39
Problem Description
Marry likes to count the number of ways to choose two non-negative integers $a$ and $b$ less than $m$ to make $a \times b$ mod $m \neq 0$.
Let's denote $f(m)$ as the number of ways to choose two non-negative integers $a$ and $b$ less than $m$ to make $a\times b$ mod $m \neq 0$.
She has calculated a lot of $f(m)$ for different $m$, and now she is interested in another function $g(n)=\sum\limits_{m|n}f(m)$. For example, $g(6)=f(1)+f(2)+f(3)+f(6)=0+1+4+21=26$. She needs you to double check the answer.
Give you $n$. Your task is to find $g(n)$ modulo $2^{64}$.
Let's denote $f(m)$ as the number of ways to choose two non-negative integers $a$ and $b$ less than $m$ to make $a\times b$ mod $m \neq 0$.
She has calculated a lot of $f(m)$ for different $m$, and now she is interested in another function $g(n)=\sum\limits_{m|n}f(m)$. For example, $g(6)=f(1)+f(2)+f(3)+f(6)=0+1+4+21=26$. She needs you to double check the answer.
Give you $n$. Your task is to find $g(n)$ modulo $2^{64}$.
Input
The first line contains an integer $T$ indicating the total number of test cases. Each test case is a line with a positive integer $n$.
$1 \le T \le 20000$
$1 \le n \le 10^9$
$1 \le T \le 20000$
$1 \le n \le 10^9$
Output
For each test case, print one integer $s$, representing $g(n)$ modulo $2^{64}$.
Sample Input
2 6 514
Sample Output
26 328194