Description

对于数列 $a$，其满足以下性质：

1. $|a_1|=1$
2. $|a_k|=|a_{k-1}+1|$，其中 $k\geq 2$ 且 $k$ 为正整数。

希望你对于每一个正整数 $n$，得到一个数列 $a$ 使得 $|\sum\limits_{i=1}^na_i|$ 的值最小。输出这个最小值。

Format

Input

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

接下来 $T$ 行，每行一个正整数 $n$，如题目描述所示。

Output

共 $T$ 行，每行输出一个答案，如题目描述所示。

Samples

3
2
3
2020

1
0
2

Limitation

对于 $100\%$ 的数据，$1\leq T\leq 10^5$，$1\leq n\leq 10^{18}$。

样例解释

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

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