Given a number A which is an X base number system value, please convert it to decimal (based on 10). For each digit K in A, we use (K) to represent it.
For example, given A = (2)(50)(30) based on 60 number system, then its decimal value is 2*60² + 50*60¹+30*60⁰  which is 7200 + 3000 + 30 = 10230 

The first line contains an integer T which is the number of cases.
In the following T line, there are two fields in each line, the first field is the number and the second field is the base. 
(you can assume all are positive integers and no spaces in the number for input)

For each case, output the decimal value  (the value is less than 10¹⁵ )