Light Bulb Sequence

The stage for the next Hunger Games opening ceremony is being prepared. One of the decorations is a row of light bulbs hanging above the stage. The row has $n$ bulbs, numbered from $1$ to $n$.

All bulbs start off. During the ceremony, the bulbs will be operated on $k$ times. During the $i$-th operation ($1 \le i \le k$), the state of every bulb whose number is divisible by $i$ is flipped: an off bulb turns on, and an on bulb turns off. For a reason known only to the chief designer, $n$ does not exceed $10k$.

The chief designer wants to know how many bulbs are still on after all operations. Help him.

The number of bulbs and the number of operations are not yet final. There are $t$ possible cases, and the designer gave a list of $t$ pairs $n_i$ and $k_i$. For each case, print the number of bulbs that are on at the end.

The first line contains an integer $t$ ($1 \le t \le 100$), the number of possible cases. Each of the next $t$ lines contains $n_i$ and $k_i$ ($1 \le n_i \le 10^{18}$, $1 \le k_i \le 10^{18}$, $n_i \le 10k_i$).

Print $t$ lines, each containing the answer for one case.