작은 수

꼬마 블라드는 좋아하는 두 수 $a$와 $b$를 가지고 있다. 최근 학교에서 나눗셈과 곱셈을 배운 그는 곧바로 좋아하는 수를 나누고 곱하기 시작했다.

그는 공책에 $a$와 $b$를 적고, 두 수에 적용할 수 있는 세 가지 연산을 생각해 냈다.

• 두 수를 공약수 하나로 나눈다.
• $a$를 $a$의 약수 $g$ 하나로 나누고, $b$에 $g$를 곱한다.
• $b$를 $b$의 약수 $g$ 하나로 나누고, $a$에 $g$를 곱한다.

연산을 한 번 수행할 때마다 그는 기존의 수를 지우고 새로운 수로 바꾼다. 연산을 계속할지 그만둘지는 그가 정한다.

블라드는 어리기 때문에 수가 작아지기를 바란다. 그래서 $a+b$를 최소로 만들려고 하지만 혼자서는 해내지 못한다. 이 연산들로 얻을 수 있는 합의 최솟값을 구하고, 그 합을 가지는 최종 $a$와 $b$의 예를 하나 제시하자.

입력은 여러 테스트 케이스로 이루어진다. 첫째 줄에 테스트 케이스의 수 $t$가 주어진다 ($1 \le t \le 500$).

각 테스트 케이스는 한 줄에 두 정수 $a$와 $b$로 주어진다 ($1 \le a, b \le 10^9$). 이는 블라드가 좋아하는 수이다.

각 테스트 케이스마다 한 줄에, 위 연산들로 얻을 수 있는 합이 최소인 순서쌍 하나를 출력한다.