Given a decimal integer n and a base k, translate n to the corresponding k-based number.
The first line contains an integer t (1 <= t <= 100), which indicates the number of test cases in the input. Each test case is given in a line, containing two integers n and k (n <= 10000000, k<=9).
case1: n<=100
case2: n<=10000
case3: n<=100000
case4: n<=10000000
Output the number in base k.