1.
Division Given two numbers a and b, use a more efficient algorithm (taught in class) to print the quotient and remainder of a/b.

Input

The first line will contain a number t. The next t lines contain two numbers a and b.

Output

For each test case, print the intermediate quotient after each iteration. Print one more line at the end with the final quotient and remainder seperated by spaces.

Sample Input

2
53 5
36 8

Sample Output

1
2
5
10
10 3
1
2
4
4 4

Constraints

0=a,b=100000000(10^8)
2.
Fibonacci Given a number n, print the nth fibonacci number. The first 2 numbers of the fibonacci sequence are 0 and 1.

Input

The first line contains a number t which denotes the number of test cases. Each of the next t lines contain an integer n

Output

The output must contain exactly t lines such that the output on the ith line is the remainder of the respective fibonacci number when divided by 100000 (10^5).

Sample Input

3
3
5
100

Sample Output

1
3
69026

Constraints

0n=10000(10^4