¡°WTF! While everyone has his girl(gay) friend, I only have my keyboard!¡± Tired of watching others' affair, Hillan burst into scream, which made him decide not to hold it back.
¡°All right, I am giving you a question. If you answer correctly, I will be your girl friend.¡± After listening to Hillan, Girl replied, ¡°What is the value of $\sum_{i=1}^n\sum_{j=1}^mf\left(i,j\right)$, where $f\left(i,j\right)=0$ if $\gcd\left(i,j\right)$ is a square number and $f\left(i,j\right)=1$ if $\gcd\left(i,j\right)$ is not a square number($\gcd\left(i,j\right)$ means the greatest common divisor of x and y)?¡±
But Hillan didn't have enough Intelligence Quotient to give the right answer. So he turn to you for help.
Input
The first line contains an integer $T\left(1\leq T\leq10,000\right)$¡ª¡ªThe number of the test cases.
For each test case, the only line contains two integers $n,m\left(1\leq n,m\leq10,000,000\right)$ with a white space separated.
Output
For each test case, the only line contains a integer that is the answer.
Sample Input
2
1 2333333
10 10
Sample Output
0
33
Hint
In the first test case, obviously $f\left(i,j\right)$ always equals to 0, because $i$ always equals to 1 and $\gcd\left(i,j\right)$ is always a square number(always equals to 1).
