Conventional number systems of fixed-radix r consisting of digits that are in range {0, 1, …, r – 1}. The interpretation rule for calculating the numerical value of the sequence (x_n-1, x_n-2, … , x₀) is</p>

[X = \sum_{i=0}^{n-1}{x_ir^i}]

We are interested in implementing a computer program to convert 8-digit, radix 32 numbers to radix 10 and radix 2 numbers, respectively. The following ranges R₂, R₁₀ and R₃₂ are sets of possible digits for radix 32, 10 and 2 systems, respectively.

• R₂ = {0, 1}
• R₁₀ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
• R₃₂ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V}

The first number n (1<= n <= 100) indicates the number of test cases. Then n radix 32 numbers are entered. Each radix number is no more than 8 digits.

출력 형식

For each input, two integers are printed on a separate lines indicating a radix 10 number followed by a radix 2 number of the given radix 32 number.

예제 입력

4
32
A7
CAT
ALL41

예제 출력

98
0001100010
327
0101000111
12637
011000101011101
11195521
0101010101101010010000001