Given positive integers $n, r$, find
\begin{equation}
\sum_{d = 1}^{n}{(-1)^{\left\lfloor \sqrt{d~\times~r~\times~d} \right\rfloor}}
\end{equation}
Input
The first line contains a number $T$, representing that there are $T$ test cases.
The next $T$ lines, each line contains two positive integers $n, r$.
Output
Output $T$ lines, each line containing an integer representing the answer.
Examples
input
3 3 5 3 6 3 7
output
3 1 -1
Constraints
For 30% of the data, $n \leq 10^5, r \leq 10^2, T \leq 10$;
For 60% of the data, $n \leq 10^7, r \leq 10^3, T \leq 10^2$;
For 100% of the data, $n \leq 10^9, r \leq 10^4, T \leq 10^4$.