题目描述

2333 表达发自内心的大笑。 2333 来源于猫扑网，因为猫扑网的表情编号 233 是一个大笑 锤地的表情。后来233 广泛传播用于表达发自内心的大笑，3 越 多则表达的越强烈。 2333 通过b 站得到了推广，而b 站的站娘都是22 和33，这 或许也是一种巧合2333 现在，给定一个有规律的数列的规律，询问该数列的第n 项 是多少？ 这个数列由 2 和3 构成他们的前10 项为: $2,3,3,2,2,2,3,3,3,2…$ 或许你并不明白这是个什么玩意，聪明的2233 娘告诉你： 这个数列由233 开头，可以把数列中连续相同的数字看成一个 整体。 $（2）,(33),(222),(333),(22),(33)…$ 并且你把括号内的数个数写出来后还能得到原来的数列: （2） (33) (222) (333) (22) (33)… 2 3 3 2 2… 第一个(2)下面没有对应的数。 (33)有两个 3 说明原来的数列开头是2，(222)有3个2 说明 原来的数列第二项是3。(333)有3个3 说明原来的数列第三项 是3…括号内的 2，3 是交替出现的。 你可以简单的发现它们每一项跟前面的项都是相关的。 虽然33 是机器人但是她的运算速度似乎不够尽人意，现在 她会给你多组询问，让你来回答每组询问的答案。

输入格式

输入包含多组数据。 第一行T (1 ≤ T ≤10^5) 代表数据总数。 每一组询问包含一个n (1 ≤ n ≤10^7) 为询问的第n 项。

输出格式

对于每组询问输出一行即为第n 项。

样例

4 
1 
2 
3 
1000000

2 
3 
3 
3

提示

解决这个问题或许会得到 33 娘的好感哦~

by 董国梁 录入