Problem Description

Bob is playing a matrix game. He needs to deal with a matrix of $n$ rows and $m$ columns, satisfying the properties below:

$\qquad \cdot$ Both rows and columns are numbered from $1$

$\qquad \cdot$ All the elements in the matrix have only two values: $0$ and $1$

$\qquad \cdot$ All the elements equals $0$ initally

To play the game, Bob can apply $\operatorname{flip} (i,j)$ operations to the matrix. This operation can flip all elements whose row number is a multiple of $i$ \textbf{and} column number is a multiple of $j$ (flipping an element means change its value from $v$ to $1-v$). Bob is very bold when playing games. He always performs $\operatorname{flip}$ operations on all the positive integer pairs $(i,j)$.

After finishing all the operations, Bob wants to know how many elements which equals $1$ there are in the matrix.

Input

The first line is a single number $T$, indicating the number of test cases.

In the following $T$ lines, the $i$-th line contains two integers $n, m$, representing the number of rows and columns of the $i$-th matrix, respectively.

It is guaranteed that $1 \le T \le 10$ and $1 \le n, m \le 10^{18}$.

Output

$T$ lines, the $i$-th line a single integer - the answer of the $i$-th matrix.

2
1 1
2 3

1
1