408350: GYM103104 A CRC Test

In the process of data transmission, bit errors ($$$0$$$ becomes $$$1$$$, $$$1$$$ becomes $$$0$$$) may be caused by various interferences, which may lead to the receiver receiving the wrong data. CRC (Cyclic Redundancy Check) is a widely used algorithm to check whether there are errors in data transmission.

Specifically, CRC will select a predetermined $$$k+1$$$ bits integer $$$P$$$, and add $$$k$$$ redundancy bits as verification code after the $$$n$$$-bits data to be transmitted, so that the last transmitted $$$n + k$$$ bits data can be divisible by $$$P$$$ in modulo $$$2$$$ division.

About modulo $$$2$$$ division: the characteristic of modulo $$$2$$$ operation is that it does not consider carry and borrow. Among them, module $$$2$$$ addition is equivalent to module $$$2$$$ subtraction and bitwise XOR; The modular $$$2$$$ division method is equivalent to replacing all subtractions in vertical calculation with modulo $$$2$$$ subtraction.

Now, given the divisor $$$P$$$ used by cyclic check and the data transmitted, please calculate the verification code added in this transmission.

The first line of the input contains an integer $$$T \;(1 \leq T \leq 1000)$$$, denotes the number of testcases.

The first line of each test case contains a $$$k+1 \;(4\leq k\leq 32)$$$ bits binary number $$$P$$$, indicates the divisor used for cyclic verification.

The second line of each test case contains an $$$n$$$-bits$$$(1\leq n \leq 4000)$$$ hexadecimal number $$$x$$$, indicates the data to be transmitted.

For each test case, output one line containing a binary number with a length of exactly $$$k$$$, representing the verification code of the data transmission you calculated.

3
110101
28D
100000111
1F1E33
100000111
ABCDEF123456

01110
11111101
10000010