ACM ICPC 的评委们非常小心，防止题目泄露，所有的通信都是加密的。然而，人们有时会犯错，比如使用过于薄弱的加密方案。这里就是一个例子。
所选的加密方式非常简单：通过根据共享密钥翻转某些位来加密输入的每一块。为了提供合理的安全性，块和密钥的大小均为 32 位。
也就是说，假设输入是一个由 $m$ 个 32 位整数组成的序列： $N_1 \quad N_2 \quad N_3 \quad \dots \quad N_m$
使用密钥 $K$ 编码后，它变成了以下 $m$ 个 32 位整数的序列： $(N_1 \wedge K) \quad (N_2 \wedge K) \quad (N_3 \wedge K) \quad \dots \quad (N_m \wedge K)$ 其中 $(a \wedge b)$ 是 $a$ 和 $b$ 的按位异或（bitwise exclusive or）。
异或是一个逻辑运算符，当且仅当其操作数中只有一个为 1 时，结果为 1，否则为 0。以下是它对 1 位整数的定义： $0 \oplus 0 = 0 \quad 0 \oplus 1 = 1$ $1 \oplus 0 = 1 \quad 1 \oplus 1 = 0$
正如你所见，它等同于模 2 加法。对于两个 32 位整数 $a$ 和 $b$，它们的按位异或 $a \wedge b$ 定义如下（使用由 0 和 1 组成的二进制表示）： $a \wedge b = a_{31} \dots a_1 a_0 \wedge b_{31} \dots b_1 b_0 = c_{31} \dots c_1 c_0$ 其中 $c_i = a_i \oplus b_i \quad (i = 0, 1, \dots, 31)$。
例如，使用二进制表示，$11010110 \wedge 01010101 = 10100011$，或者使用十六进制，$d6 \wedge 55 = a3$。
由于这种加密方式在统计攻击面前极其脆弱，消息必须提前压缩，使其不具有统计规律。我们假设 $N_1 \quad N_2 \quad \dots \quad N_m$ 已经是压缩后的形式。
然而，问题在于压缩算法本身引入了某种规律：每 8 个压缩数据整数后，它会插入一个校验和，即这些整数的和。也就是说，在上述输入中，$N_9 = \sum_{i=1}^{8} N_i = N_1 + \dots + N_8$，其中加法是模 $2^{32}$ 的。
幸运的是，你可以拦截评委之间的通信。也许它包含决赛的题目！
正如你非常聪明，你肯定已经发现可以轻松找到密钥的最低位，记为 $K_0$。一方面，如果 $K_0 = 1$，那么编码后，$\sum_{i=1}^{8} N_i \wedge K$ 的最低位保持不变（因为 $K_0$ 被加了偶数次），但 $N_9 \wedge K$ 的最低位发生了改变，所以它们会不同。另一方面，如果 $K_0 = 0$，那么编码后，$\sum_{i=1}^{8} N_i \wedge K$ 的最低位将与 $N_9 \wedge K$ 的最低位相同，因为它们没有改变。例如，如果编码后的最低位是 $1 \quad 1 \quad 1 \quad 1 \quad 1 \quad 1 \quad 1 \quad 1 \quad 1$，那么 $K_0$ 必须为 1；但如果它们是 $1 \quad 1 \quad 1 \quad 1 \quad 1 \quad 1 \quad 1 \quad 0 \quad 1$，那么 $K_0$ 必须为 0。
到目前为止，一切顺利。你能做得更好吗？
你应该找出用于编码的密钥。
输入格式
输入的第一行包含一个正整数 $S$，表示输入中的数据集数量。$S$ 不超过 1000。
随后是 $S$ 个数据集。每个数据集由 9 个 32 位整数组成，对应通信的前 9 个块。它们以十六进制表示，使用数字 ‘0’ 到 ‘9’ 和小写字母 ‘a’ 到 ‘f’，且没有前导零。它们由空格或换行符分隔。每个数据集以换行符结束。
输出格式
对于每个数据集，你应该输出用于编码的密钥。每个密钥应单独占一行，并以十六进制表示，使用数字 ‘0’ 到 ‘9’ 和小写字母 ‘a’ 到 ‘f’，且没有前导零。
样例
输入 1
8 1 1 1 1 1 1 1 1 8 3 2 3 2 3 2 3 2 6 3 4 4 7 7 b a 2 2e e1 13 ce 28 ca 6 ab 46 a6d b08 49e2 6128 f27 8cf2 bc50 7380 7fe1 723b 4eba eb4 a352 fd14 6ac1 eed1 dd06 bb83 392bc ef593c08 847e522f 74c02b9c 26f3a4e1 e2720a01 6fe66007 7a4e96ad 6ee5cef6 3853cd88 60202fb8 757d6d66 9c3a9525 fbcd7983 82b9571c ddc54bab 853e52da 22047c88 e5524401
输出 1
0 2 6 1c6 4924afc7 ffff95c5 546991d 901c4a16