“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.
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.
For each test case, the only line contains a integer that is the answer.