题目背景

在 01 世界里寻觅......

题目描述

小 b 得到了一个长度为 $n$ 的二进制字符串 $s$。

小 b 会按以下方式化简：

当 $n > 1$ 时，构造一个新的长度为 $n-1$ 的字符串 $s^*$，其中对于所有 $i \in [1, n-1]$，$s^*_i = s_i \oplus s_{i+1}$。

令 $s = s^*$，继续化简直到 $n = 1$。

这里 $\oplus$ 表示“按位异或”操作。换句话说，新字符串的每一位是原字符串 $s$ 中相邻两位模 $2$ 的和。

经过 $n-1$ 次化简后，此时字符串长度变为 $1$，小 b 请你帮他输出最后的字符串。

输入格式

本题单个测试点内有多组测试数据。

第一行是一个正整数 $T$，表示测试数据组数。接下来对每组数据，按如下格式输入：

第一行包含一个由字符 0 和 1 组成的二进制字符串 $s$。

保证单个测试点内 $\left |s\right |$ 之和 $\sum \left |s\right | \leq 10^6$。

输出格式

每组测试数据，一行一个字符 0 或 1，表示化简后的字符串。

输入输出样例 #1

输入 #1

2
1010
1101

输出 #1

0
1

说明/提示

对于 $20\%$ 的数据，满足 $\sum \left |s\right | \leq 10$；

对于 $50\%$ 的数据，满足 $\sum \left |s\right | \leq 5000$；

对于 $100\%$ 的数据，满足 $\sum \left |s\right | \leq 10^6$。

对于所有数据，满足 $1\le T\le 10$。