| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem D
Fibonacci Gcd
Time Limit: 1000ms
Memory Limit: 65536kb Description
Fibonacci sequence: 1 1 2 3 5 8 13 …defined as follows: Gcd (a, b): greatest common divisor of a and b. Now give you two numbers n and m, Can you find Gcd (f(n), f(m))? Assuming X= Gcd (f(n), f(m)), Now your task is to find the first five digits and the last eight digits of X. For example，if X=1234567890，you should output 12345 34567890; If X=1234, you should output 1234 1234. Input
The first line, an integer T, representing T test cases below. (T<=100).
For each test case, two numbers n, m are given. (1<=n, m<=10^9).
Output
For each case, output the first five digits and the last eight digits of Gcd (f(n), f(m)), separated by one space.
Sample Input
1 4 7 Sample Output
1 1 |