← 返回题目列表

Codeforces · 2009/E

E. 克利的超级大阵列!!!

中文机器翻译题面 查看原题

Klee 有一个长度为 $$$n$$$ 的数组 $$$a$$$,其中包含按顺序排列的整数 $$$[k, k+1, ..., k+n-1]$$$。 Klee 希望选择一个索引 $$$i$$$ ($$$1 \leq i \leq n$$$) 使得 $$$x = |a_1 + a_2 + \dots + a_i - a_{i+1} - \dots - a_n|$$$ 最小化。注意,对于任意整数$$$z$$$,$$$|z|$$$表示$$$z$$$的绝对值。

输出 $$$x$$$ 的最小可能值。

输入

第一行包含 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq n, k \leq 10^9$$$) — 数组的长度和数组的起始元素。

输出

对于每个测试用例,在新行中输出 $$$x$$$ 的最小值。

示例

输入 #1

4
2 2
7 2
5 3
1000000000 1000000000

输出 #1

1
5
1
347369930

注意

在第一个示例中,$$$a = [2, 3]$$$。当选择 $$$i = 1$$$ 时,$$$x = |2-3| = 1$$$。可以证明这是 $$$x$$$ 的最小可能值。

在第三个示例中,$$$a = [3, 4, 5, 6, 7]$$$。当选择 $$$i = 3$$$ 时,$$$x = |3 + 4 + 5 - 6 - 7| = 1$$$。可以证明这是 $$$x$$$ 的最小可能值。