Nhập vào hai số \(n\) và \(m\). Hãy tìm ước chung lớn nhất của số Fibonacci thứ \(n\) và \(m\)

Chỗ Fibonacci có dạng sau: \(F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-1}\)

Ví dụ: \(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...\)

Input

• Dòng 1: \(t\) số lượng bộ test
• \(t\) dòng tiếp theo: mỗi dòng chứa hai số \(n\) và \(m\)

Sample Input 1

2
3 6
6 9

Sample Output 1

2
2