让我们表示正确的火柴方程(我们将其表示为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(| |+| | | |=| | | | | |)。