分糖果
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

汤姆和杰瑞在一场生日聚会中得到了n袋糖果(n为偶数),糖果袋中分别有,,…,颗糖果,出于礼貌,他们无法将这些已分好的糖果进行拆分。现在他们想将糖果袋分成两份(每份有袋糖果),为了尽量公平,希望两份糖果之间的差值为最小。例如:第一份糖果含a颗糖果,第二份含b颗糖果,请你们帮助他们使的值为最小。

注意:糖果袋中的糖果不能分开,为一个整体。

输入描述:

第一行一个正整数T,代表测试组数。
接下来的T行每行一个整数n

输出描述:

T行,每行一个整数,代表每组数据所对应的两份糖果的最小差值。

由于输出结果过大,结果对取模。
示例1

输入

复制
5
2
4
6
100
1000

输出

复制
2
6
14
131961966
233992933

备注: