Description

肖哥在一家公司干活，公司中一共有n个老板。肖哥已经打了20年工了。如今，肖哥想要放假！肖哥找到了公司的老板们诉了一下苦。老板们经过商讨，决定给他假期。但是，所有老板打算和他玩个游戏，如果他玩到了最后，就给他假期。

游戏规则如下:

所有人围坐在一个圆桌上。从第一个人开始数数，（默认他的编号为1号，接下来每一个人的编号依次加1，达到所玩游戏的人数上限截止），每数到f的人出局，下一个人在从一号开始数，数到f的值人出局。直到最后只剩下一个人，游戏结束。然而f值是一个变量，即每出局了一个人，从下一个人开始数数，这个时候这轮的f值更新成一个新的f值了。每轮f的值满足如下规则:

默认f[0]=1 , f[1]=2； f值变化的规则：f[n] = f[n-2] + f[n-1]；

即第一轮最开始的f值是f[1],第一个人从1开始数，数到f[1]的人出局，下一个人重新从1开始数，数到f[2]的人出局......直到剩下最后一个人。

肖哥想知道在那个位置可以留到最后，从而获得假期！

Input Format

第一行一个整数T(0 <= T <= 1e5)，表示T组数据；

接下来每行一个整数N( 0 < N < 40)表示公司中老板的人数。

Output Format

一共T行，每行一个整数，表示肖哥在那个位置可以留到最后。输出他的编号即可。

1
2

1

2
3
6

4
1

Source

1816 Online Judge 10.100.0.232