I just found the easiest and funny sequence ever !

Your task is simple. Just write a program to find the Nth term of this sequence!!

The sequence is as follows::

3, 8, 12, 17, 22, 28, 35....

Input

First line contains t = number of test cases

and then next t lines follow n. 

1<=n<=10^11

Note-- Value of n is modified to encourage better solutions!

Output

Just the output the nth term modulo 123456789

Example

Input:
3
1
2
3

Output:
3
8
12