Given a decimal integer n and a base k, translate n to the corresponding k-based number.
Input
The first line contains an integer t (1 <= t <= 20), 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).