QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100

# 12. Sum

统计

给定正整数 $n, r$,求

\begin{equation} \sum_{d = 1}^{n}{(-1)^{\left\lfloor \sqrt{d~\times~r~\times~d} \right\rfloor}} \end{equation}

输入格式

第一行一个数 $T$,表示有 $T$ 组测试数据。

接下来 $T$ 行,每行两个正整数 $n, r$。

输出格式

输出 $T$ 行,每行一个整数表示答案。

样例一

input

3
3 5
3 6
3 7

output

3
1
-1

限制与约定

对于 30% 的数据,满足 $n \leq 10^5, r \leq 10^2, T \leq 10$;

对于 60% 的数据,满足 $n \leq 10^7, r \leq 10^3, T \leq 10^2$;

对于 100% 的数据,满足 $n \leq 10^9, r \leq 10^4, T \leq 10^4$。