← 返回题目列表

Codeforces · 1223/A

A. 芝商所

中文机器翻译题面 查看原题

让我们用一个方程 $$$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$$$ (||+||||=||||||)。