You have an N x M matrix, where 1 to N are rows and 1 to M are columns.

Element at the intersection of $i^{th}$ row and $j^{th}$ column is equal to $F(i+j)$, where $F(x)$ is equal to the number of prime divisors of x.

Determine the sum of all the elements of the matrix.

Input

• The first line contains an integer T denoting the number of test cases.
• For each test case, the first line contains two space-separated integers N, M.

Output

For each test case, print the sum of all the elements of the matrix  in a new line.

Constraints

$1 ≤ T ≤ 10 \\ 1 ≤ N, M ≤10^6$