최대공약수

두 정수의 최대공약수(GCD) 는 두 수를 나머지 없이 나누는 가장 큰 양의 정수입니다. 예를 들어 8과 12의 최대공약수는 4입니다. 두 양의 정수의 최대공약수를 구하는 프로그램을 작성하세요.

첫째 줄에 문제의 개수를 나타내는 양의 정수 $n$이 주어집니다. 이어지는 각 문제에는 두 양의 정수가 하나 이상의 공백으로 구분되어 주어집니다. 입력에 빈 줄은 없습니다.

각 문제에 대해 두 양의 정수의 최대공약수를 한 줄에 하나씩 출력합니다.