Leaky Cryptography#3197

Leaky Cryptography

5 secondi

64 megabyte

Difficile

The ACM ICPC judges are very careful to avoid leaking their problems, and all communications are encrypted. However, sometimes mistakes happen, such as using too weak an encryption scheme. Here is an example of such a case.

The chosen encryption was very simple: encrypt each chunk of the input by flipping some bits according to a shared key. To provide reasonable security, the size of both the chunk and the key is 32 bits.

That is, suppose the input was a sequence of $m$ 32-bit integers:

$N [1] N [2] N [3] \dots N [m]$ N[1]\ N[2]\ N[3]\ \ldots\ N[m]

After encoding with the key $K$ , it becomes the following sequence of $m$ 32-bit integers:

$(N [1] \oplus K) (N [2] \oplus K) (N [3] \oplus K) \dots (N [m] \oplus K)$ (N[1]\ \oplus\ K)\ (N[2]\ \oplus\ K)\ (N[3]\ \oplus\ K)\ \ldots\ (N[m]\ \oplus\ K)

where $a \oplus b$ a \oplus b is the bitwise exclusive or (xor) of $a$ and $b$ .

Exclusive or is the logical operator which is 1 when only one of its operands is 1, and 0 otherwise. Here is its definition for 1-bit integers:

As you can see, this is identical to addition modulo 2. For two 32-bit integers $a$ and $b$ , their bitwise exclusive or $a \oplus b$ a \oplus b is defined as follows, using their binary representations composed of 0's and 1's:

$a \oplus b = a [31] \dots a [1] a [0] \oplus b [31] \dots b [1] b [0] = c [31] \dots c [1] c [0]$ a \oplus b = a[31] \ldots a[1] a[0]\ \oplus\ b[31] \ldots b[1] b[0] = c[31] \ldots c[1] c[0]

where

For example, using binary notation, $11010110 \oplus 01010101 = 10100011$ 11010110 \oplus 01010101 = 10100011, or in hexadecimal, $d 6 \oplus 55 = a 3$ d6 \oplus 55 = a3.

Since this kind of encryption is weak to statistical attacks, the message must be compressed in advance, so that it has no statistical regularity. We suppose that $N [1] N [2] \dots N [m]$ N[1]\ N[2]\ \ldots\ N[m] is already in a compressed form.

However, the problem is that the compression algorithm itself introduces a form of regularity: after every 8 integers of compressed data, it inserts a checksum, the sum of these integers. That is, in the above input,

$N [9] = N [1] + \dots + N [8]$ N[9] = N[1] + \ldots + N[8]

where additions are modulo $2^{32}$ 2^{32}.

Fortunately, you have managed to intercept a communication between the judges. Maybe it contains a problem for the finals!

Since you are very clever, you have surely noticed that you can easily find the lowest bit of the key, written as $K [0]$ . On one hand, if $K [0] = 1$ K[0] = 1, then after encoding, the lowest bit of $Σ_{1 \leq i \leq 8} (N [i] \oplus K)$ \Sigma_{1 \leq i \leq 8}(N[i] \oplus K) is unchanged, as $K [0]$ is added an even number of times, but the lowest bit of $N [9] \oplus K$ N[9] \oplus K changes, so they must be different. On the other hand, if $K [0] = 0$ K[0] = 0, then after encoding, the lowest bit of $Σ_{1 \leq i \leq 8} (N [i] \oplus K)$ \Sigma_{1 \leq i \leq 8}(N[i] \oplus K) is still identical to the lowest bit of $N [9] \oplus K$ N[9] \oplus K, since they do not change. For example, if, after encoding, the lowest bits are $111111111$ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1, then $K [0]$ must be 1, but if they are $111111101$ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 0\ 1, then $K [0]$ must be 0.

So far, so good. Can you do better?

You must find the key used for encoding.

Input

The input starts with a line containing a positive integer $S$ , the number of datasets in the input. $S \leq 1000$ S \leq 1000.

It is followed by $S$ datasets. Each dataset consists of nine 32-bit integers, corresponding to the first nine chunks of a communication. They are written in hexadecimal notation, using digits '0' to '9' and lowercase letters 'a' to 'f', without leading zeros. They are separated by a space or a newline. Each dataset ends with a newline.

Output

For each dataset, output the key used for encoding. Each key should appear alone on its line and be written in hexadecimal notation, using digits '0' to '9' and lowercase letters 'a' to 'f', without leading zeros.

Esempi

Esempio 1