Once again Atul is in trouble. He was going through his old mathematics book where he found a strange series, called fibbonacci numbers(Fibonacci series or numbers are sequence in which nth number is sum of previous two numbers look here ), he thought is easy to find the numbers if previous numbers are given whats fun in it, but what if N is given and have to find Nth fibbonacci number.Since Atul is weak at studies he ask you as his programmer to help him out. Can you help Atul to solve this problem?

below is fibbbacci series

INPUT

First line contains T no of test cases where 1<T<1000000

Next T lines contains term number N ; where 1<N<10000000

OUTPUT

Each test case output Nth term of fibbonacci series.

NOTE

Fibbonacci series to be used for quetsion is 1,1,2,3,5,8,13........