Number Base Conversion

Time Limit: 1 Second Memory Limit: 32768 KB

We programmer are familiar with binary system, hexadecimal system and of course decimal system, right? And number base conversion between them is an interesting and easy task. It is not hard to figure out that the same method works for any other number bases. Then, let's take a look at another kind of number system.

In ordinary number system, e.g. decimal system whose base number is 10, exactly 10 digits from 0 to 9 are allowed. In general, B-Base-Number-System allows B digits from 0 to B-1. But what about if we allow some negative digits?

For simplicity, we distribute B digits evenly on both side of 0, e.g. B for 5, five digits namely -2,-1,0,1,2 are allowed. But when it comes to even number of B, we can't do it evenly so we'll not consider Even-Base-Number-System.

Let's look at some conversions, 6(dec) can be written as 11 in this number system of B for 5 because 6 = 1*5^1 + 1*5^0. What about 4(dec)? Maybe it seems a little strange but we can really write it as 1-1 because 4 = 1*5^1 + (-1)*5^0. Someone argues that 4 also can be written as -(-11) as long as -((-1)*5^1 + 1*5^0) really equals 4, but I think -(-11) must be a "negative" number, inconsistence with original positive number, so 1-1 is prefered.

And here comes the problem, you are asked to write a program to automate the conversions.

Input

The first line of input contains a single positive integer T, the number of testcases, followed by T testcases. Each testcase is made up of two integers: the base number B(3<=B<=123, B is odd) and the original positive decimal number N(0<N<10^32).

Output

Print the representation in one line.

NOTE: If B is 123, the 123 allowed digits is -z,-y,-x, ... ,-b,-a,-Z,-Y,-X, ... ,-B,-A,-9,-8, ... ,-2,-1,0,1,2, ... ,9,A, ... ,Z,a, ... ,y,z.

Sample Input

Sample Output

1-1
21
1-2

Submit

Source: ZOJ Monthly, October 2004