Secret Code

The sarcophagus is locked by a secret numerical code. To open it you must know the code and set it exactly on top of the sarcophagus; if an incorrect code is entered, the tickets inside catch fire immediately and are lost forever. The code consists of up to 100 integers.

An archaeologist obtained a copy of the code. Afraid that it might fall into the wrong hands, he encoded the numbers in a special way. He chose a complex number $B$ whose absolute value is greater than that of every number to be encoded. He then treated the sequence $a_n, a_{n-1}, \dots, a_1, a_0$ as the digits of the positional numeral system with base $B$, encoding them as the single number

$$X = a_0 + a_1 B + a_2 B^2 + \cdots + a_n B^n$$

Given the number $X$ and the base $B$, recover the digits $a_0, a_1, \dots, a_n$ that express $X$ in base $B$.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains four integers $X_r, X_i, B_r, B_i$ ($|X_r|, |X_i| \le 1000000$, $|B_r|, |B_i| \le 16$), where $X = X_r + X_i i$ and $B = B_r + B_i i$. Here $B$ is the base of the system ($|B| > 1$) and $X$ is the number to express.

For each test case, print a single line containing the digits $a_n, a_{n-1}, \dots, a_1, a_0$ separated by commas. The digits must satisfy all of the following:

• $0 \le a_i < |B|$ for every $i$
• $X = a_0 + a_1 B + a_2 B^2 + \cdots + a_n B^n$
• if $n > 0$ then $a_n \ne 0$
• $n \le 100$

The representation satisfying these conditions is unique. If no such representation exists, print exactly The code cannot be decrypted.