Not So Flat After All

Any positive integer v can be written as p₁^a₁ · p₂^a₂ · … · p_n^a_n, where p_i is a prime number and a_i ≥ 0. For example: 24 = 2³ · 3¹.

Pick any two prime numbers p₁ and p₂ where p₁ ≠ p₂. Imagine a two-dimensional plane where the powers of p₁ are plotted on the x-axis and the powers of p₂ on the y-axis. Now any number that can be written as p₁^a₁ · p₂^a₂ can be plotted on this plane at location (x, y) = (a₁, a₂). The figure below shows a few examples where p₁ = 3 and p₂ = 2.

This idea can be extended for any N-dimensional space where each of the N axes is assigned a unique prime number. Each N-dimensional space has a unique set of primes. We call such set the Space Identification Set or S for short. |S| (the ordinal of S) is N.

Any number that can be expressed as a multiplication of p_i ∊ S (each raised to a power a_i ≥ 0) can be plotted in this |S|-dimensional space. The figure at the bottom illustrates this idea for N = 3 and S = {2, 3, 7}. Needless to say, any number that can be plotted on space A can also be plotted on space B as long as S_A ⊂ S_B.

We define the distance between any two points in a given N-dimensional space to be the sum of units traveled to get from one point to the other while following the grid lines (i.e., movement is always parallel to one of the axes.) For example, in the figure below, the distance between 168 and 882 is 4.

Given two positive integers, write a program that determines the minimum ordinal of a space where both numbers can be plotted in. The program should also determine the distance between these two integers in that space.

Input Specification

Your program will be tested on one or more test cases. Each test case is specified on a line with two positive integers (0 < A, B < 1 000 000), where A · B > 1.

The last line is made up of two zeros.

Output Specification

For each test case, print the following line:

k. X:D

Where k is the test case number (starting at one), X is the minimum ordinal needed in a space in which both A and B can be plotted, and D is the distance between these two points.

Sample Input

1. 168 882
2. 770 792
3. 0 0

download as text file

Output for Sample Input

1. 1. 3:4
2. 2. 5:6

download as text file