#### Start

2017-10-13 15:30 UTC

## 2017 Atlantic Canadian Preliminary Contest

#### End

2017-10-13 20:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -831 days 5:16:52

5:00:00

0:00:00

# Problem EIntegrity for spies

Two friends decide to communicate with each other using a secret code over numbers from $0$ to $b-1$. Each message can be arbitrarily long, but it must be validated using the following formula:

$\mbox{current value of the message} = (\mbox{value of the message read so far})*b + \mbox{new number read}.$

The current value of the message at the end of the message must be a multiple of $k$.

## Input

The input starts with $n$, the number of test cases, on a line by itself. The remainder of the file contains $n$ test cases. Each test case consists of $b$, $m$ (the number of messages in this test case), and $k$ on lines by themselves, followed by $m$ messages one per line, each line terminated by a $-1$. You may assume $2 \leq b \leq 36$. Schematically, the input looks like

n
b_1
m_1
k_1
message 1 of test case 1
...
message m1 of test case 1
...
b_2
m_2
k_2
m_2 messages of test case 2
the other n-2 test cases


## Output

Output is a sequence of $0$’s and $1$’s, $1$ for valid messages and $0$ for those that are non-valid, i.e., $n$ binary strings (each of length $m_ i$ for test case $i$). Messages with numbers larger than $b-1$ should be considered invalid.

Sample Input 1 Sample Output 1
3
4
10
5
3 0 0 0 0 0 0 -1
3 0 0 0 0 0 1 -1
3 0 0 0 0 0 2 -1
3 0 0 0 0 0 3 -1
3 0 0 0 0 1 0 -1
1 0 0 0 1 -1
2 0 0 0 4 -1
2 0 0 0 1 -1
2 0 0 0 2 -1
2 0 0 0 3 -1
6
7
5
1 0 0 0 0 0 2 -1
1 0 0 3 0 0 2 -1
1 0 0 0 1 -1
2 0 0 0 4 -1
2 0 0 0 1 -1
2 0 0 0 2 -1
2 0 0 0 3 -1
4
6
5
1 0 0 0 1 0 2 -1
2 0 0 1 0 0 2 -1
3 0 1 0 0 0 2 -1
1 1 0 0 0 0 2 -1
1 1 0 0 0 0 0 -1
1 1 0 0 0 0 1 -1

0010000001
0000001
000010


Sample Input 2 Sample Output 2
2
17
4
101
5 16 -1
5 15 -1
11 15 -1
2 1 5 1 -1
33
3
1234
1 4 13 -1
1 9 12 10 4 -1
1 9 12 10 5 -1


1011
110