Under construction

Still being built. Things may change

What base is this?

Interview

Time limit2sMemory limit512 MB

Summary
For each digit string, print its value read as octal, decimal, and hexadecimal; if it has an 8 or 9, print 0 for the octal value.
Level

Easy3 of 10

Topics
Implementation, Math, String, Brute force
Solved
No attempts yet

Problem

Languages such as C, C++, and Java let you write a constant in several bases by putting a prefix character in front of it.

An octal constant starts with the digit 0, a hexadecimal constant starts with 0x, and a decimal constant takes no prefix. Written that way, the decimal number 4660 looks like this.

  • octal: 011064
  • decimal: 4660
  • hexadecimal: 0x1234

Without the prefix a compiler has no way to tell which base was meant. Drop the 0x from 0x1234 and the compiler may read the digits as octal or as decimal, even though the person who typed them meant hexadecimal.

Assume that mistake has happened. Given strings made only of the digits 0 through 9, read each string as an octal number, as a decimal number, and as a hexadecimal number.

Input

The first line contains the number of test data T (1 ≤ T ≤ 10000).

Each of the next T lines contains an integer K, the number of that test data, and a string, separated by a space. The string consists only of the digits 0 through 9, its length is between 1 and 7, and it may start with 0.

Output

For each test data print one line holding K, then the value of the string read as an octal number, as a decimal number, and as a hexadecimal number, in that order and separated by spaces. Write all three values in decimal.

If the string contains an 8 or a 9 it cannot be read as an octal number, so print 0 in place of the octal value.

Examples7

  1. Example 1

    Input
    4
1 1234
2 9
3 1777
4 129
    Expected output
    1 668 1234 4660
2 0 9 9
3 1023 1777 6007
4 0 129 297

  2. Example 2

    Input
    1
1 0
    Expected output
    1 0 0 0

  3. Example 3

    Input
    10
1 0
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
    Expected output
    1 0 0 0
2 1 1 1
3 2 2 2
4 3 3 3
5 4 4 4
6 5 5 5
7 6 6 6
8 7 7 7
9 0 8 8
10 0 9 9

  4. Example 4

    Input
    3
1 0000000
2 0000001
3 0000010
    Expected output
    1 0 0 0
2 1 1 1
3 8 10 16

  5. Example 5

    Input
    4
1 0011064
2 0011065
3 0000129
4 0007777
    Expected output
    1 4660 11064 69732
2 4661 11065 69733
3 0 129 297
4 4095 7777 30583

  6. Example 6

    Input
    3
1 7777777
2 9999999
3 1000000
    Expected output
    1 2097151 7777777 125269879
2 0 9999999 161061273
3 262144 1000000 16777216

  7. Example 7

    Input
    5
1 80
2 08
3 88888
4 70707
5 77777
    Expected output
    1 0 80 128
2 0 8 8
3 0 88888 559240
4 29127 70707 460551
5 32767 77777 489335