기약분수

분수 $a/b$는 정수 $a$와 $b$로 나타내는 유리수다. $a$를 분자, $b$를 분모라고 하고 분모는 0이 될 수 없다.

분자와 분모를 0이 아닌 같은 수로 나누면 값이 같은 분수를 얻는다. 이것을 약분이라고 한다. 분자와 분모가 서로소인 분수, 즉 둘을 동시에 나누는 양의 정수가 1뿐인 분수를 기약분수라고 한다. 예를 들어 $3/9$는 3과 9가 모두 3으로 나누어떨어지므로 기약분수가 아니다. 반면 $3/8$은 3과 8을 동시에 나누는 양의 정수가 1뿐이므로 기약분수다.

주어진 분수를 기약분수로 고치는 프로그램을 작성하시오.

첫째 줄에 분수의 개수 $n$이 주어진다. ($1 \le n \le 10^4$)

다음 $n$개의 줄에는 분수 하나의 분자 $a$와 분모 $b$가 공백을 사이에 두고 주어진다. ($1 \le a \le 10^6$, $1 \le b \le 10^6$)

입력에 주어진 순서대로 각 분수의 기약분수를 한 줄에 하나씩 출력한다. 분자와 분모는 공백 하나로 구분한다.