Cathy have some questions, and she doesn’t know how to do it, she asks you to help her, because she knows that you are clever enough. You have learned complete binary tree in the class, now, it comes to complete k-ary tree. You’re given two integer n and k, and you are asked to print the path from the root to the n-th node in complete k-ary tree from the root to leaf.
The first line will be an integer T, which is the number of test cases. (1 <= T <= 105). For each test case, the first line will be two integer n(1 <= n <= 1018) and k(1 <= k <= 1018).
For each test output the path from root to the n-th node. There is a space between two values, and there is no space in the end of a line.
3
8 2
7 3
15 41 2 4 8
1 2 7
1 4 15
Nodes are numbered from 1