Problem Description

Jerry is fond of functions. He thinks the mystery of the universe is hidden behind the notations, variables and numbers.
Of all functions, he thinks $\gcd$ and $\lfloor x\rfloor$ are the most fascinating, and that something combines gcd with truncation should be even more marvelous.
Therefore, he comes up with a problem: calculate

Input

The input contains several test cases.
The first line contains an integer $T(1\le T\le 11)$, the number of test cases.
Each of the next $T$ lines contains a integer $n(1\le n\le 10^{21})$, indicating a query.

Output

For each test case, output one line containing an integer indicating the corresponding answer.

10
64
180
526
267
775
649
749
908
300
255

103
327
1069
522
1693
1379
1631
1998
606
492

Hint

g++ compiler on HDOJ supports __int128. And you may need the following function:

template <class T>
void read(T &x) {
  static char ch;static bool neg;
  for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
  for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
  x=neg?-x:x;
}