让我们表示正确的火柴方程（我们将其表示为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。不幸的是，你可能使用了所有的火柴但是仍无法组成CME。但你可以买一些额外的火柴，然后组装成CME！
注意：加号和等号不需要消耗火柴棒
例如，如果n=2，则可以购买两个火柴并装配成|+|=| |；如果n=5，则可以购买一个火柴并装配| |+|=| | | 。
计算组装CME时必须购买的最小火柴数。
输入
第一行包含一个整数q（1≤q≤100）-测试用例数。
每个测试用例的唯一一行包含一个整数n（2≤n≤10^9）-火柴数。
输出
对于每个测试用例，在一行中打印一个整数-组装CME时必须购买的最小匹配数。
Example
input
4
2
5
8
11
output
2
1
0
1
注意
第一个和第二个测试用例已在说明中解释。
在第三个测试用例中，您可以在不购买匹配项的情况下组合成1+3=4（|+| | |=| | | |）。
在第四个测试用例中，购买一个火柴并组合成2+4=6（| |+| | | |=| | | | | |）。
