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×b mod m≠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×b mod m≠0.
She has calculated a lot of f(m) for different m, and now she is interested in another function g(n)=∑m|nf(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 264.
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≤T≤20000
1≤n≤109
Output
For each test case, print one integer s, representing g(n) modulo 264.
Sample Input
2
6
514
Sample Output
26
328194
