[Login|Register]
Problems

Status

Rank

Problem 1263
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
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.3ms with 1 query(s).