고장난 통신탑

2050년 부산대학교의 캠퍼스에는 셀 수 없이 많은 통신탑들이 서 있다. 원래 서로 다른 통신탑끼리 1 대 1로 통신이 가능했으나, 비가 찬란히 내리는 날에 통신탑이 싫었던 학생들이 몰래 모든 통신탑들의 정수 처리 부분을 망치로 고장냈다. 통신탑을 수리하고 싶었지만, 수리 완료에 $1000$년이나 걸려 일단 고장 난 통신탑을 사용하기로 했다. 고장 난 통신탑의 특징은 다음과 같다.

• 각각의 통신탑은 1번부터 자연수로 무한하게 식별 번호가 주어져 있다. $i$번 통신탑의 식별 번호는 $i$이다.
• $a$번 통신탑과 $b$번 통신탑이 있을 때, 두 식별 번호의 쌍 $(a, b)$가 약수 관계일 때 두 통신탑 간 직접 통신이 가능하다. 약수 관계란 두 수의 쌍 $(a,b)$ 중 큰 수를 작은 수로 나눴을 때 나머지가 0인 관계다.
• 1번 통신탑이 식별 번호가 짝수 번호인 통신탑과 통신할 때 드는 직접 통신 비용은 모두 2이며, 그 외 모든 통신에 드는 직접 통신 비용은 모두 1이다.
• $a$번 통신탑과 $c$번 통신탑 사이에 통신이 가능하고, $c$번 통신탑과 $b$번 통신탑 사이에 통신이 가능하면 $a$번 통신탑과 $b$번 통신탑은 $c$번 통신탑을 거쳐 통신이 가능하다. 이때 통신 비용은 각각의 통신에 드는 통신 비용의 합이다.

이때 부산대학교의 총장인 산지니는 통신 비용을 줄이기 위해 임의의 통신탑 $a$와 $b$ 사이의 통신 비용이 최소화되는 통신 경로를 구하는 프로그램을 만들기로 했다. 산지니는 추가로 프로그램의 통신 로그 관리를 최적화하기 위해 통신 비용이 최소화되는 경로가 여러 가지 있다면, 통신 경로 위의 통신탑들의 식별 번호들의 합이 최소인 경로를 구하기로 했다. 하지만, 산지니는 귀찮아서 부산대학교의 알고리즘 동아리 PULSE에 이 일을 떠넘기고 3시간 안에 만들지 않으면 동아리를 해체하겠다고 협박한 뒤 프로그램 제작을 떠넘겼다. 알고리즘 동아리 PULSE의 해체를 막기 위해 최대한 빨리 프로그램을 제작하자. 문제의 입력 조건 내에서 들어올 수 있는 임의의 입력에 대해 경로 선택 조건을 만족하는 통신 경로는 유일하다.

첫 번째 줄에 테스트 케이스의 개수 $T(1≤T≤10^5)$가 주어진다.

두 번째 줄부터 $T+1$번째 줄까지 두 통신탑의 식별 번호 쌍 $(a,b)(1≤a,b≤2\times10^7,a≠b)$가 한 칸 띄어서 주어진다.

입력에 들어오는 수는 모두 정수이다.

첫 번째 줄부터 $T$번째 줄까지 차례대로 각 테스트 케이스에 대한 정답을 출력한다.

정답을 출력할 때는 $a$와 $b$를 포함하여 통신 경로 위에 있는 통신탑의 식별 번호를 한 칸씩 띄어 $a$부터 순서대로 출력한다.

이 문제는 입력해야 할 정보와 출력해야 할 정보의 양이 방대하므로 각 언어의 빠른 입출력의 사용을 권장한다.