Z 在玩扑克牌。

小 Z 把牌两两分成 n 组，第 i 组的两张牌分别写着 $a_i$ 和 $b_i$ 。

小 Z 有一个神秘非负整数 K ，他可以选择至多 K 个 i ，交换 $a_i$, $b_i$ 。

小 Z 想要最大化 A + B ，其中 A 是交换之后所有 ai 的 AND ，B 是交换之后

所有 bi 的 AND 。这里的 AND 是按位与，即 & 。

1.2 Input Format

为了方便操作，所有 ai, bi 都以二进制的形式给出。

第一行一个正整数 T ，表示数据组数。每组数据的输入格式如下：

第一行一个正整数 K 和一个非负整数 K 。

接下来 n 行，每行两个 01 串，表示 ai, bi 。从左到右依次是高位到低位，且除了 0 以外不存在前导零。

1.3 Output Format

对于每组数据，输出一行一个二进制数表示答案，除了 0 以外不允许有前导零。

1.4 Sample 1 Input

3
1 1
1011011 101101
2 0
1011011 0
0 101101
5 2
1101 11011
11101 11111
11011 1111
10111 1001
1011 10101

1.5 Sample 1 Output

10001000
0
11010

1.6 Sample 2,3

见下发文件。

1.7 Constraints

本题采用子任务捆绑测试

设 S 表示一组数据中所有 01 串的长度之和

对于所有数据，保证 ∑ n ≤ 2 × 106, ∑ S ≤ 4 × 106, 0 ≤ K ≤ n

Subtask 1 (20 points) ：∑ n ≤ 500 ，01 串的长度不超过 9

Subtask 2 (20 points) ：∑ n ≤ 2000, ∑ S ≤ 4000

Subtask 3 (20 points) ：K = n

Subtask 4 (40 points) ：无特殊限制