생각보다 평평하지 않은 공간

모든 양의 정수 $v$ 는 $v = p_1^{a_1} \cdot p_2^{a_2} \cdots p_n^{a_n}$ 꼴로 쓸 수 있다. 여기서 각 $p_i$ 는 소수이고 모든 $a_i \ge 0$ 이다. 예를 들어 $24 = 2^3 \cdot 3^1$ 이다.

서로 다른 두 소수 $p_1 \ne p_2$ 를 고르자. $p_1$ 의 지수를 x좌표, $p_2$ 의 지수를 y좌표로 삼는 2차원 평면을 생각하면, $p_1^{a_1} \cdot p_2^{a_2}$ 꼴의 수는 모두 점 $(a_1, a_2)$ 로 나타낼 수 있다.

이 아이디어는 임의의 $N$차원 공간으로 확장된다. 각 축에는 서로 다른 소수가 하나씩 배정된다. 이렇게 각 공간이 갖는 고유한 소수 집합을 공간 식별 집합(Space Identification Set) $S$ 라 하며, 그 크기 $|S|$ 는 $N$ 과 같다. $S$ 에 속한 소수들만의 곱(각 소수의 지수는 $\ge 0$)으로 표현되는 수는 이 $|S|$차원 공간 위의 한 점으로 나타낼 수 있다. 또한 $S_A \subseteq S_B$ 이면 공간 $A$ 에 나타낼 수 있는 수는 공간 $B$ 에도 나타낼 수 있다.

두 점 사이의 거리는 격자선을 따라 한 점에서 다른 점까지 이동하는 데 필요한 단위 이동 횟수로 정의한다. 모든 이동은 한 축에 평행하다. 이는 두 좌표 벡터 사이의 맨해튼(L1) 거리와 같다. 예를 들어 $168 = 2^3 \cdot 3 \cdot 7$ 과 $882 = 2 \cdot 3^2 \cdot 7^2$ 사이의 거리는 $|3-1| + |1-2| + |1-2| = 4$ 이다.

두 양의 정수가 주어질 때, 두 수를 모두 나타낼 수 있는 공간의 최소 크기와, 그 공간에서 두 수 사이의 거리를 구하는 프로그램을 작성하라.

입력은 하나 이상의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 양의 정수 $A$ 와 $B$ ($0 < A, B < 1{,}000{,}000$, $A \cdot B > 1$)가 공백으로 구분되어 한 줄에 주어진다. 마지막 줄에는 두 개의 0이 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

k. X:D

여기서 $k$ 는 테스트 케이스 번호(1부터 시작), $X$ 는 $A$ 와 $B$ 를 모두 나타낼 수 있는 공간의 최소 크기, $D$ 는 그 공간에서 두 수 사이의 거리이다.