题目描述

Fibonacci 数列，大家应该都很熟悉了吧? ^_^

Fibonacci 数列是这样定义的：

F[0]=0;

F[1]=1;

F[n]=F[n-1]+F[n-2], for n>1

大家都知道 Fibonacci 数列的增长速度是惊人的。当 n=47 时，F[47]=2971215073（>$2^{31}$）。由于数列的值增长太快，对于 n，你只需要输出 F[n]%12 。

输入格式

第一行，一个整数 T ($1 \le T \le 100$）

之后 有 T 行，每一行有一个整数 $n(0 \le n \le 2 \times 10^8 )$

输出格式

对于每一组测试数据 n ，输出一个整数 m=F[n]%12 。

样例

4
0
1
2
47

0
1
1
1