Time Limit: 1s
Memory Limit: 128MB
피보나치 수열이란, 1, 1에서 시작해서 앞의 두 수를 더해나가는 수열이다.
피보나치 수열은 1, 1, 2, 3, 5, 8, ... 로 진행된다.
a번째 피보나치 수와 b번째 피보나치 수의 최대공약수를 구해보자.
Line 1: 입력의 수 N (1≤a,b≤100000)
Line 2~N: 두 개의 자연수 a, b (1≤a,b≤1000) 단, 답은 long long int 범위를 넘지 않는다.
2 3 5 8 12
1 3
* a와 b의 최대공약수는 a%b와 b의 최대공약수와 같습니다.
* a번째 피보나치 수와 b번째 피보나치 수의 최대공약수는 (a와 b의 최대공약수)번째 피보나치 수와 같습니다.