Skip to content
UniCircle
Menu
Sign inJoin
MediumCodingNumber systems

Convert a number between any two bases (2 to 36)

Question PROG-CNV-105

Convert each number from base from to base to. Digits above 9 are the letters A–Z (A = 10, …, Z = 35). Print results in uppercase without leading zeros (zero is 0).

Values go up to 10^18. That is more than a JavaScript Number can hold exactly (2^53 ≈ 9 × 10^15), so JavaScript solutions need BigInt.

Constraints

  • 1 ≤ T ≤ 1000
  • 2 ≤ from, to ≤ 36
  • 0 ≤ value ≤ 10^18; input digits are uppercase and valid for their base.

Input and output

Input
First line: T. Then T lines `number from to`.
Output
T lines, each the number written in base `to`.

Examples

Input 1

3
255 10 16
FF 16 2
1010 2 10

Output

FF
11111111
10

255 = FF in hex = 11111111 in binary; 1010 in binary is 10.

Input 2

2
ZZ 36 10
0 7 3

Output

1295
0

ZZ = 35 × 36 + 35 = 1295. Zero is 0 in every base.

Show hints
  • First convert to a plain integer: value = value * from + digit (Horner's rule).
  • Then repeatedly take value % to for the next digit (least significant first) and divide by to. Reverse at the end.
Show the explanation

Go through an integer, so that you only need two simple conversions instead of 35 × 35 special cases.

String → integer (Horner's rule). v = 0; for each digit d: v = v * from + d. The digit value is c - '0' for 0–9 and c - 'A' + 10 for letters.

Integer → string. If v is 0, the answer is "0". Otherwise, while v > 0: append DIGITS[v % to] and set v /= to. The digits come out least significant first, so reverse them at the end.

Range of integer types: the real interview point

  • C++: 10^18 < 2^63 − 1 ≈ 9.22 × 10^18, so long long (or unsigned long long) is enough. The intermediate v * from stays within range because it never exceeds the final value.
  • JavaScript: Number is a 64-bit float with 53 bits of mantissa. Above 2^53, integers are silently rounded. Use BigInt (10n, BigInt(x)) for the arithmetic.
  • Python: integers have arbitrary precision. int(s, base) does the first step, but there is no built-in for converting to arbitrary bases (only bin, oct, hex, and format(v, "x")).

Edge cases: the value 0, converting to the same base (the output still loses any leading zeros), and base 36 using every letter. Shortcut worth mentioning: converting between bases that are powers of 2 (binary, octal, hex) can be done by regrouping bits, 3 per octal digit and 4 per hex digit.

Original UniCircle question. Last reviewed 22 Oct 2026.