CF1223A.CME

Let's denote correct match equation (we will denote it as CME) an equation $a + b = c$ there all integers $a$, $b$ and $c$ are greater than zero.

For example, equations $2 + 2 = 4$ (||+||=||||) and $1 + 2 = 3$ (|+||=|||) are CME but equations $1 + 2 = 4$ (|+||=||||), $2 + 2 = 3$ (||+||=|||), and $0 + 1 = 1$ (+|=|) are not.

Now, you have $n$ matches. You want to assemble a CME using all your matches. Unfortunately, it is possible that you can't assemble the CME using all matches. But you can buy some extra matches and then assemble CME!

For example, if $n = 2$, you can buy two matches and assemble |+|=||, and if $n = 5$ you can buy one match and assemble ||+|=|||.

Calculate the minimum number of matches which you have to buy for assembling CME.

Note, that you have to answer $q$ independent queries.

我们称一个“正确的匹配方程”（以下简称 CME）为形如 $a + b = c$ 的等式，其中所有整数 $a$、$b$ 和 $c$ 均为正整数。

例如，等式 $2 + 2 = 4$（表示为 ||+||=||||）和 $1 + 2 = 3$（表示为 |+||=|||）是 CME；但等式 $1 + 2 = 4$（|+||=||||）、$2 + 2 = 3$（||+||=|||）以及 $0 + 1 = 1$（+|=|）不是 CME。

现在你有 $n$ 根火柴棒。你想用全部这些火柴棒拼出一个 CME。遗憾的是，可能无法恰好用 $n$ 根火柴棒拼出一个 CME。但你可以额外购买若干根火柴棒，然后用所有（原有加新购）火柴棒拼出一个 CME！

例如，若 $n = 2$，你可以购买 2 根火柴棒，拼出 |+|=||；若 $n = 5$，你可以购买 1 根火柴棒，拼出 ||+|=|||。

请计算为拼出一个 CME 所需购买的最少火柴棒数量。

注意：你需要回答 $q$ 个相互独立的查询。

The first line contains one integer $q$ ($1 \le q \le 100$) — the number of queries.

The only line of each query contains one integer $n$ ($2 \le n \le 10^9$) — the number of matches.

第一行包含一个整数 $q$（$1 \le q \le 100$）—— 查询次数。

每个查询仅有一行，包含一个整数 $n$（$2 \le n \le 10^9$）—— 比赛场数。

For each test case print one integer in single line — the minimum number of matches which you have to buy for assembling CME.

对于每个测试用例，在单独一行中输出一个整数——组装 CME 所需购买的火柴棒的最少数量。

The first and second queries are explained in the statement.

In the third query, you can assemble $1 + 3 = 4$ (|+|||=||||) without buying matches.

In the fourth query, buy one match and assemble $2 + 4 = 6$ (||+||||=||||||).

第一和第二个查询在题目描述中已作说明。

在第三个查询中，无需购买火柴即可拼出 $1 + 3 = 4$（|+|||=||||）。

在第四个查询中，购买一根火柴，拼出 $2 + 4 = 6$（||+||||=||||||）。