Maaz is a very flirty boy. Once he was sitting in the mess and two girls, Ishika and Kashish came and sat behind him. Maaz being naughty thought he has a chance to make one of them as future partner!! So he decided to entertain girls with his favourite subject maths. He said to girls that he will tell a number 'n' and Ishika needs to answer the difference between the nth Fibonacci number modulo 123456789, and the nth prime number, and Kashish needs to speak out their sum. Both girls being fool enough started playing with Maaz.

Fibonacci Series: 0, 1, 1, 2, 3 ...

Prime numbers: 2, 3, 5, 7 ...

Now your task is to calculate the modulus of both the values and print them.

Well, MAAZ loves Kashish more!!

Input

First line contains t, the number of test cases and next t lines contain a single number n.

1 <= n <= 5761460

Output

Two numbers as described separated by a space.

Example

Input:
1
10

Output:
5 63