ANARC09C  Not So Flat After All
Any positive integer v can be written as p_{1}^{a1} ∗ p_{2}^{a2} ∗ . . . ∗ p_{n}^{an} where pi is a prime number and ai ≥ 0. For example: 24 = 2^{3} ∗ 3^{1} .
Pick any two prime numbers p1 and p2 where p_{1} != p_{2} . Imagine a two dimensional plane where the powers of p_{1} are plotted on the xaxis and the powers of p_{2} on the yaxis. Now any number that can be written as p_{1}^{a1} ∗ p_{2}^{a2} can be plotted on this plane at location (x, y) = (a1 , a2 ). The figure on the right shows few examples where p_{1} = 3 and p_{2} = 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 pi ∈ S (each raised to a power (ai ≥ 0) can be plotted in this SDimensional 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 also determines the distance between these two integers in that space.
Input
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 of two zeros.
Output
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 that both A and B can be plotted in. D is the distance between these two points.
Example
Input:
168 882
770 792
0 0
Output:
1. 3:4
2. 5:6
hide comments
shashank3395:
20181002 07:36:21
getting SIGSEGV provide me some test cases to be tested upon


sahil_1994:
20170818 21:22:17
is normal factorization way to go for this problem ?


sak3t:
20170101 11:19:26
Got it in 0.00 and 8.2 Mem :D 

justforpractic:
20161030 17:30:38
the images aren't loaded and i don't understand the problem 

Sarthak Munshi:
20160605 08:36:08
image not visible ! 

try2catch:
20160324 04:49:48
Cook meggi in rest of the time :D 

omjego:
20160119 15:51:28
Images are not loading


hodobox:
20160115 19:24:42
If I end my program when (A*B==0) I get WA, but when I end it if (A==0&&B==0) I get AC, even though it states all test cases have A * B > 1... 

Jaswanth:
20150402 08:33:10
Can reduce the time limit of this problem it is far more than needed 

Sahil Dua:
20141104 12:32:04
AC in 0.21s

Added by:  Mohammad Kotb 
Date:  20091128 
Time limit:  32.12s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  http://www.icpcanarc.org 