让我们用一个方程 $$$a + b = c$$$ 来表示正确的匹配方程(我们将其表示为 CME),其中所有整数 $$$a$$$、$$$b$$$ 和 $$$c$$$ 都大于零。
例如,方程 $$$2 + 2 = 4$$$ (||+||=||||) 和 $$$1 + 2 = 3$$$ (|+||=|||) 是 CME,但方程 $$$1 + 2 = 4$$$ (|+||=||||)、$$$2 + 2 = 3$$$ (||+||=|||) 和 $$$0 + 1 = 1$$$ (+|=|) 不是。
现在,您有 $$$n$$$ 匹配项。您想用所有火柴组装一个 CME。不幸的是,您可能无法使用所有火柴组装 CME。但你可以购买一些额外的火柴,然后组装 CME!
例如,如果$$$n = 2$$$,您可以购买两根火柴并组装|+|=||,如果$$$n = 5$$$,您可以购买一根火柴并组装||+|=|||。
计算组装 CME 时必须购买的最少火柴数量。
请注意,您必须回答 $$$q$$$ 独立查询。
输入
第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 100$$$) — 查询数。
每个查询的唯一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^9$$$) — 匹配数。
输出
对于每个测试用例,在一行中打印一个整数 - 您必须购买用于组装 CME 的最小火柴数量。
示例
输入 #1
4 2 5 8 11
输出 #1
2 1 0 1
注意
第一个和第二个查询在语句中进行了解释。
在第三个查询中,您可以在不购买火柴的情况下组装$$$1 + 3 = 4$$$ (|+|||=||||)。
在第四个查询中,购买一根火柴并组装 $$$2 + 4 = 6$$$ (||+||||=||||||)。