数字根

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

话说我们定义一个数的“数字根”R(n),表示将该数所有位数反复求和,直到剩下小于10的数,例如R(29876)=R(32)=R(5)

现在输入一个数n,求F(n)的数字根,其中F(n)定义如下

F(n)=0                      n=0

F(n)=1                      n=1

F(n)=F(n-1)+F(n-2)            n>1

Input

第一行输入T<10000,表示case数。每个case输入一个数n,0<=n<=10^18。

Output

输出一个数,表示R(F(n))

Sample Input

2
1
10

Sample Output

1
1

Hint

Source

from friend

提交代码