Migrated from Lutece 3029 再见了，所有的签到题

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

第一次打ACM时 并没有什么特别的感觉 因为独属于我的签到题 我早已遇见

恭喜你即将完成暑假前集训的所有专题训练，就让这道题成为我的告别礼物，希望我们可以在暑假集训再次相遇。 求：

$\sum_{d=1}^n (-1)^{\lfloor d\sqrt r \rfloor}$。

多组询问。

Input

第一行一个整数$T$，表示有$T$组测试数据。 接下来$T$行，每行两个整数$n,r$.

Output

共$T$行，每行一个整数，表示答案。

Samples

3
3 5
3 6
3 7

3
1
-1

Constraints

$1\leq T\leq 10^4$, $1\leq n\leq 10^9$, $1\leq r\leq 10^4$.

Resources

2023 UESTC ICPC Training for Math