Checksum

To guarantee the correctness of transmitted data, a checksum is sometimes attached to it. Imagine the following way of computing a checksum.

Given a message $M$ (as a bit string), we choose a checksum generator $G$ (also a bit string) and append to the end of $M$ a number of zeros equal to the number of bits of $G$ minus $1$. This gives the extended message $M'$. Interpreting the digits of $M'$ and $G$ as coefficients of polynomials over the field $\mathbb{F}_2$ (the most significant bit is the coefficient of the highest power of the variable), we compute the remainder of dividing the polynomial corresponding to $M'$ by the polynomial corresponding to $G$. The sequence of coefficients of that remainder is called the checksum of the message $M$.

Your task is to compute the checksum of the message $M$. For certain reasons we trust the checksum more when the generator, interpreted as a binary number, is a prime, so compute the checksum only in that case. If the generator is not a prime, print the word ERROR.

The first line contains an integer $T$ ($1 \le T \le 10^3$), the number of test cases. Each of the next $T$ lines contains a single test case, consisting of two bit strings separated by a single space. The first bit string is the message $M$ (its length does not exceed $512$ bits); the second is the generator $G$ (its length does not exceed $48$ bits). Neither $M$ nor $G$ has leading zeros.

For each test case, print on its own line the corresponding checksum as a decimal number (without leading zeros), unless the generator is not a prime — in that case print the word ERROR on that line.

About the field $\mathbb{F}_2$

By $\mathbb{F}_2$ we mean the set $\{0, 1\}$ with addition $+$ and multiplication $\cdot$ defined as follows.

• $1 + 1 = 0 + 0 = 0$ and $1 + 0 = 0 + 1 = 1$
• $1 \cdot 0 = 0 \cdot 1 = 0 \cdot 0 = 0$ and $1 \cdot 1 = 1$

Moreover, in $\mathbb{F}_2$ we have $-1 = 1$ and $-0 = 0$. This leads to the perhaps surprising conclusion that subtracting a number is equivalent to adding it, e.g. $0 - 1 = 0 + 1 = 1$ and $1 - 1 = 1 + 1 = 0$.

When operating on polynomials with coefficients in $\mathbb{F}_2$ we proceed analogously, e.g. $(x^3 + x + 1)(-x - 1) = (x^3 + x + 1)(x + 1) = x^4 + x^2 + x + x^3 + x + 1 = x^4 + x^3 + x^2 + 1$.

Worked examples

A generator whose binary value is composite yields the answer ERROR. For instance $100$, $110$, and $1000$ are the binary representations of the composite numbers $4$, $6$, and $8$.

For a prime generator we compute the checksum. For example, with $M = 1101$ and $G = 10$ we have $M' = 11010$, whose polynomial is $W_{M'}(x) = x^4 + x^3 + x$ and $W_G(x) = x$. Dividing $W_{M'}$ by $W_G$ over $\mathbb{F}_2$ gives quotient $x^3 + x^2 + 1$ and remainder $0$, so the checksum is $0$.

With $M = 1000$ and $G = 11$ we have $M' = 10000$, whose polynomial is $W_{M'}(x) = x^4$ and $W_G(x) = x + 1$. Dividing gives quotient $x^3 + x^2 + x + 1$ and remainder $1$, so the checksum is $1$.