SP26978 HC10000 - Hofstadter–Conway 10000 dollar sequence

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 $ .

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} $ ).

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