Description

One day, WD found a very strange combination lock. He remembered that before CX asked him to unlock it, CX told him some numbers. Unfortunately, since WD is really bad at this, he forgot what those numbers were. He only remembers that after numbering them from $1$ to $n$, for any positive integer $d(1\le d\le n)$, the sum of all numbers whose indices are multiples of $d$ is exactly $\mu(d)$ (that is, the Möbius function value of $d$).

Now, to open this lock, he must know the number at position $m$. Since he cannot do anything, he asks you for help.

Input Format

The first line contains an integer $T$, indicating the number of test cases. The next $T$ lines each contain two integers $n,m$.

Output Format

Output $T$ lines. Each line contains one integer, representing the value of the $m$-th number. It can be proven that the answer is unique.

2
5 1
5 2

4
-1

Hint

$subtask1(21pts):~n\le 10^6,~T\le 5$.

$subtask2(34pts):~n\le 10^7,~T\le 10$.

$subtask3(45pts):~n\le 10^{18},~m\le 10^9,~\frac{n}{m}\le 10^9,~T\le 20$.

For all testdata, $m\le n$.

For sample 1, the sequence that satisfies the requirement is 4 -1 -1 0 -1.

Translated by ChatGPT 5