#y1016. sequence2

sequence2

Description

对于数列 aa,其满足以下性质:

  1. ∣a1∣=1|a_1|=1
  2. ∣ak∣=∣ak−1+1∣|a_k|=|a_{k-1}+1|,其中 k≥2k\geq 2 且 kk 为正整数。

希望你对于每一个正整数 nn,得到一个数列 aa 使得 ∣∑i=1nai∣|\sum\limits_{i=1}^na_i| 的值最小。输出这个最小值。

Format

Input

第一行一个正整数 TT,表示有 TT 组测试数据。

接下来 TT 行,每行一个正整数 nn,如题目描述所示。

Output

共 TT 行,每行输出一个答案,如题目描述所示。

Samples

3
2
3
2020
1
0
2

Limitation

对于 100%100\% 的数据,1≤T≤1051\leq T\leq 10^5,1≤n≤10181\leq n\leq 10^{18}。

样例解释

对于第一个数据,aa 数列的所有可能情况为 {1,2}\{1,2\},{1,−2}\{1,-2\},{−1,0}\{-1,0\},其中和的绝对值最小为 11,情况有 {1,−2}\{1,-2\} 和 {−1,0}\{-1,0\}。

对于第二个数据,aa 数列的所有可能情况为 {1,2,3}\{1,2,3\},{1,2,−3}\{1,2,-3\},{1,−2,1}\{1,-2,1\},{1,−2,−1}\{1,-2,-1\},{−1,0,1}\{-1,0,1\},{−1,0,−1}\{-1,0,-1\},其中和的绝对值最小为 00,情况有 {1,2,−3}\{1,2,-3\},{1,−2,1}\{1,-2,1\} 和 {−1,0,1}\{-1,0,1\}。

相关

在下列比赛中:

ACM