ACSU Programming Competition

26 September 1998

Problem 5 - A Base-ic Problem

Description

We humans use base 10 in our counting primarily because we all have 10 fingers. If we'd had 12 fingers, then we would probably use base 12. Imagine the confusion if half the population had 10 fingers, and the other half had 12. How would we decide which base to use?

The Uranoids have an even worse problem. Each Uranoid is hatched with between 1 and 31 fingers on each hand. Thus, each Uranoid has between 2 and 62 fingers. Furthermore, Uranoids are very independent, and refuse to agree on a common base to use. So each Uranoid uses a base equal to the number of fingers that he possesses. When two Uranoids are talking about numbers, each must convert from the base of the other to his own base.

Your problem is to read a number n1 in base b1, and convert it into base b2. When writing a number in base b2, use the digits 0 through 9, then the characters A through Z, then a through z. So, 0 has value 0, 1 has value 1, ..., A has value 10, B has value 11, ..., Z has value 35, a has value 36, b has value 37, ..., and z has value 61.

Example

Suppose we wish to convert the number 2654 from base 10 to base 16. The base 16 representation is A5E, because

  2654 = 10 * 16^2 + 5 * 16^1 + 14 * 16^0

Recall that A has value 10 and E has value 14.

Now suppose we wish to convert the number 2654 from base 10 to base 62. The base 16 representation is go, because

  2654 = 42 * 62^1 + 50 * 62^0

Recall that g has value 42 and o has value 50.

Input / Output

The first line of input is the number of data sets. This number will be non-negative.

Each data set consists of three "integers", n1, b1, and b2. You are to output the message

	n1 base b1 = n2 base b2

where n1, b1, and b2 are given above, and n2 is the base b2 representation of n1 in base b1. The numbers n1 and n2 must be written with the most significant digit first.

n1 and n2 will have, at most, 20 digits. b1 and b2 will always be in the range 2 to 62, inclusive, represented in base 10.

Sample

Sample Input

3
2654 10 16
2654 10 62
11100100110110001010 2 9

Sample Output

2654 base 10 = A5E base 16
2654 base 10 = go base 62
11100100110110001010 base 2 = 1677724 base 9

Solution

Here is the solution by Alexsey Kliger in C++.

Here is the test input:

12
2654 10 16
A5E 16 10
2654 10 62
go 62 10
11100100110110001010 2 9
1677724 9 2
ADAM 25 10
164647 10 25
JavaSucks 62 59
T8CIHmNJw 59 62
Cornell 60 61
BcjYEJ6 61 60

Here is the correct output:

2654 base 10 = A5E base 16
A5E base 16 = 2654 base 10
2654 base 10 = go base 62
go base 62 = 2654 base 10
11100100110110001010 base 2 = 1677724 base 9
1677724 base 9 = 11100100110110001010 base 2
ADAM base 25 = 164647 base 10
164647 base 10 = ADAM base 25
JavaSucks base 62 = T8CIHmNJw base 59
T8CIHmNJw base 59 = JavaSucks base 62
Cornell base 60 = BcjYEJ6 base 61
BcjYEJ6 base 61 = Cornell base 60

Last updated 28 September 1998.

This page is maintained by Adam Florence. If there are any questions or corrections, please e-mail me.