Every integer number n is represented in positional number system of base r by a sequence of digits 0 <= d_i < r, decimal point ',' and fractional part, so the value is equal to:

n = d₀ + r * d₁ + r² * d₂ + r³ * d₃ + ... + r^-1 * d_-1 + r^-2 * d_-2 + r^-3 * d_-3 + ...

Your task is to convert a given number in r-base representation into s-base representation with l digits after decimal point (no rounding - use floor), for example: decimal 231, 5 into binary 11100111, 1 with one digit after decimal point. Assume that r <= 36 and the digits are 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, W, X, Y, Z.

Input

N [the number of series <= 1000]
n r s l [n < 36¹⁰⁰⁰ + 1, r, s <= 36, l <= 1000 ]

Output

n [s-base representation of number n]

Text grouped in [ ] does not appear in the input and output file.

Example

Input:
10
500,1 6 31 3
3866,DJ 22 27 1
EH75,L3 24 4 3
A73C,10B 13 27 2
6C6J,E483 22 6 2
JA,L 30 5 4
6,5A 20 31 2
1,C5 14 7 1
HD,6K 26 9 2
1001,011 2 10 3

Output:
5P,555
1M8H,H
301223231,320
14MB,25
1255211,35
4310,3222
6,8G
1,6
555,23
9,375