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

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