Some day in 8102, the young HRY just learned about mobius. He then made a new function:
Given n and k, output f(n,k).

Here represents . Here we give the definition of mobius:
1.
2. If n has a square factor (there exist which divides n),
3. If n is the product of odd number of different prime numbers,
The of 1,2,..,9, 10 are 1, -1, -1, 0, -1, 1, -1, 0, 0, 1 respectively.
In this problem we define .

The first line of input contains an integer T, indicating the number of test cases.
Each test case contains a line of two integers, respectively n, k.

It is guaranteed that the sum of n does not exceed .

For each test case output an integer, indicating f(n,k).

3
10 0
10 1
10 2

10
-1
7