SP6221 INCPOWK - Increasing Powers of K

Let's define S $ _{k} $ as the increasing sequence a $ _{1} $ , a $ _{2} $ , a $ _{3} $ , ... consisting of all those positive integers which are powers of K or sums of distinct powers of K. For example S $ _{3} $ = {1,3,4,9,10,12,13,27,28,30,...} Your task is given N and K find the N $ ^{th} $ term of the sequence S $ _{k} $ .

The first line of the input contains a single integer T(1

For each test case print a single line, the N $ ^{th} $ term of the sequence S $ _{k} $ .