Hofstadter–Conway $10,000 sequence is a famous sequence, which is defined as $$ a_1 = a_2 = 1,\, a_{n} = a_{a_{n-1}} + a_{n-a_{n-1}}\, (n \ge 3). $$

Your task is to find a summatory function $S(n) := \sum\limits_{i=1}^n a_i$ and compute $S(n)$ modulo $10^9$.

Input

The first line contains $T$ ($1 \le T \le 10000$), the number of test cases.

Each of the next $T$ lines contains a positive integer $n$ ($1 \le n \le 10^{18}$).

Output

For each test case, print $S(n)$ modulo $10^9$.

Example

Input:
10
1
2
3
4
5
10
100
1000
1000000
1000000000
Output:
1
2
4
6
9
32
2818
269446
334706485
137951847

Explanation

You can verify that $a_1 = a_2 = 1$, $a_3 = a_4 = 2$ and $a_5 = 3$. So, $S(5) = 9$.

$S(10^9) = 259987670137951847 \equiv 137951847 \pmod{10^9}$.

Information

There are 5 input files:

- #1: $n \le 10^{4}$, TL = 2s.

- #2: $n \le 10^{6}$, TL = 2s.

- #3: $n \le 10^{8}$, TL = 3s.

- #4: $n \le 10^{12}$, TL = 5s.

- #5: $n \le 10^{18}$, TL = 12s.

These time limits allow a (slow) Python2 solution to get accepted.