Imagine that you have only one rupee and two rupee coin with you. Given a sum “n” to pay to the shopkeeper using only these 2 coins, in how many ways can it be done? Since the answer can be pretty large, print the answer modulo “12345678901”. Also, the order in which the coins were given matters.

Input

The first line contains the number of test cases ‘t’. Then t lines follow, each having a number ‘n’.

Output

For each number ‘n’ output the corresponding answer, after modulo operation.

Constraints

T <= 10^4

1 <= N <= 10^18

Example

Sample Input
2
1
2

Sample Output
1
2