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\)