Klee 的超大数组

题目描述

你将得到一个长度为 $n$ 的数组 $a = [k, k+1, k+2, \dots, k+n-1]$。请你求出 $S$ 的值，其中

$$S = \min_{1 \le x \le n} \left| \left( \sum_{i=1}^x a_i \right) - \left( \sum_{i=x+1}^n a_i \right) \right|$$

也就是说，选择一个分割点 $x$，将数组分成前后两段，使得两段元素之和的差的绝对值最小。输出这个最小值。

输入格式

第一行包含一个正整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行包含两个用空格隔开的整数 $n$ 与 $k$。

输出格式

对于每组数据，输出一行一个整数 $S$，即所求的最小绝对值差。

样例

4
2 2
7 2
5 3
1000000000 1000000000

1
5
1
347369930

样例解释

• 第一组数据：$a = [2, 3]$。选择 $x = 1$，左半部分和为 $2$，右半部分和为 $3$，差的绝对值为 $|2-3| = 1$。可以证明这是可能的最小值。
• 第三组数据：$a = [3, 4, 5, 6, 7]$。选择 $x = 3$，左半部分和为 $3+4+5=12$，右半部分和为 $6+7=13$，差的绝对值为 $|12-13| = 1$。可以证明这是可能的最小值。

数据范围与提示

• $1 \le T \le 10^4$
• $2 \le n, k \le 10^9$

来源

Codeforces 2009E，英文题名 Klee's SUPER DUPER LARGE Array!!!。