题目描述

定义$CME$为火柴组成的正确等式$a+b=c$，$a,b,c$均为正整数。

例如，$2+2=4(∣∣+∣∣=∣∣∣∣)$，$1+2=3(∣+∣∣=∣∣∣)$是$CME$，而$2+2=3(∣∣+∣∣=∣∣∣)$，$1+2=4(∣+∣∣=∣∣∣∣)$，$0+1=1(+∣=∣)$不是$CME$。

你需要用$n$根火柴组成$CME$，可以买更多的火柴，但必须全用上。

问你最少需要买几根火柴。

输入格式

第一行是一个正整数$q$，表示询问次数。

每一个询问包含一个正整数$n$，表示你有$n$根火柴。

输出格式

对每个询问输出一个整数，表示你的答案。每一个询问占一行。

说明/提示

$1\leq q\leq100$

$2\leq n\leq 10^9$

样例

4
2
5
8
11

2
1
0
1