$\hspace{15pt}$神秘猫猫头为了能过 软件设计与体系结构 这门课，跑遍了整个学校的打印店寻找往年卷，但是他一份都没有找到。在他沮丧地走到樱花五楼下时，遇到了一个神秘商人。神秘商人看猫猫头骨骼清奇，便想和猫猫头玩一个游戏，如果猫猫头赢了，他就会用超级魔法给猫猫头变一份往年题。

$\hspace{15pt}$神秘商人的盒子里有 $n$ 个球，其中只有一个红球，其他都是白球，猫猫头和神秘商人轮流从盒中不放回地抽球，第一个抽中红球的一方获胜。神秘商人也想让猫猫头通过 软件设计与体系结构，所以他让猫猫头自己决定他时先手还是后手。猫猫头为了能拿到往年卷，他需要最大化自己获胜的概率，那么他应该要先手还是后手?

Input

$\hspace{15pt}$第一行输入一个正整数 $t(1 \leq t \leq 10^5)$，表示测试样例数量。

$\hspace{15pt}$对于每组测试样例，输入一个正整数 $n(1 \leq n \leq 10^5)$，表示盒子里球的数量。

Output

$\hspace{15pt}$对于每一组测试样例:

$\hspace{15pt}$如果先手有优势，则输出 $1$;

$\hspace{15pt}$如果后手有优势，则输出 $2$;

$\hspace{15pt}$如果先手后手都一样，则输出 $0$。

Samples

2
7
4

1
0