小女孩玛格丽塔是竞技节目的忠实粉丝。她特别喜欢有关数组及其查询的问题。
最近,她收到了一个数组 $$$a$$$,其大小为 $$$10^9$$$ 元素,填充如下:
- $$$a_1 = -1$$$
- $$$a_2 = 2$$$
- $$$a_3 = -3$$$
- $$$a_4 = 4$$$
- $$$a_5 = -5$$$
- 等等...
也就是说,数组 $$$a$$$ 的第 $$$i$$$ 元素的值是使用公式 $$$a_i = i \cdot (-1)^i$$$ 计算的。
她立即对这个数组提出了 $$$q$$$ 查询。每个查询都用两个数字描述:$$$l$$$ 和 $$$r$$$。查询的答案是数组中从 $$$l$$$ 到 $$$r$$$(含)位置的所有元素的总和。
玛格丽塔真的很想知道每个请求的答案。她不想手动计算这一切,但不幸的是,她也无法编写解决问题的程序。她转向了你——最好的程序员。
帮助她找到答案!
输入
第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^3$$$) — 查询的数量。
接下来的 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le 10^9$$$) - 查询的描述。
输出
打印 $$$q$$$ 行,每行包含一个数字 - 查询的答案。
示例
输入 #1
5 1 3 2 5 5 5 4 4 2 3
输出 #1
-2 -2 -5 4 -1
注意
在第一个查询中,您需要计算从位置 $$$1$$$ 到位置 $$$3$$$ 的数组元素之和。总和等于 $$$a_1 + a_2 + a_3 = -1 + 2 -3 = -2$$$。
在第二个查询中,您需要计算从位置 $$$2$$$ 到位置 $$$5$$$ 的数组元素之和。总和等于 $$$a_2 + a_3 + a_4 + a_5 = 2 -3 + 4 - 5 = -2$$$。
在第三个查询中,您需要计算从位置 $$$5$$$ 到位置 $$$5$$$ 的数组元素之和。总和等于 $$$a_5 = -5$$$。
在第四个查询中,您需要计算从位置 $$$4$$$ 到位置 $$$4$$$ 的数组元素之和。总和等于 $$$a_4 = 4$$$。
在第五个查询中,您需要计算从位置 $$$2$$$ 到位置 $$$3$$$ 的数组元素之和。总和等于 $$$a_2 + a_3 = 2 - 3 = -1$$$。