Your job is to take an integer x as the input and compute f(x) mod 10⁹, where f(x) is the x-th value in the well-known Fibonacci sequence. </p>

Note that Fibonacci sequence is defined as follows:

f(1) = f(2) = 1
f(k) = f(k-1) + f(k-2) for any k > 2

입력 형식

The first line of the input includes the number of test cases, 1 ≤ t ≤ 1000. Each test case is a line containing an integer 1 ≤ x ≤ 2⁴⁸.

출력 형식

For each test case, print one line containing f(x) mod 10⁹

예제 입력

11
1
2
8
20
46
60
3749999998
3749999999
3750000000
3750000001
281474976710656

예제 출력

1
1
21
6765
836311903
8755920
499999999
500000001
0
500000001
309764667