Secret Code

Time limit1sMemory limit128 MB

Summary

Convert a complex number X into base-B positional digits with a Gaussian-integer complex base, or report failure if impossible.

Level: Medium6 of 10
Topics: Math, Number theory, Implementation
Solved: No attempts yet

Problem

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$ .

Input

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.

Output

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.

Examples3

Example 1

Input

4
-935 2475 -11 -15
1 0 -3 -2
93 16 3 2
191 -192 11 -12

Expected output

8,11,18
1
The code cannot be decrypted.
16,15

Example 2
Input
```
1
2 0 3 2
```
Expected output
```
2
```
Example 3
Input
```
1
5 0 2 0
```
Expected output
```
1,0,1
```