4527 - Fibonacci GCD

• Submit
• Status
• Discuss
• Summary

Description

피보나치 수열이란, 1, 1에서 시작해서 앞의 두 수를 더해나가는 수열이다.

피보나치 수열은 1, 1, 2, 3, 5, 8, ... 로 진행된다.

a번째 피보나치 수와 b번째 피보나치 수의 최대공약수를 구해보자.

Input

Line 1: 입력의 수 N (1≤a,b≤100000)

Line 2~N: 두 개의 자연수 a, b (1≤a,b≤1000) 단, 답은 long long int 범위를 넘지 않는다.

Output

Sample Input

2
3 5
8 12

Sample Output

1
3

Hint

* a와 b의 최대공약수는 a%b와 b의 최대공약수와 같습니다.

* a번째 피보나치 수와 b번째 피보나치 수의 최대공약수는 (a와 b의 최대공약수)번째 피보나치 수와 같습니다.