题目背景
著名数学家约翰·康威（John H. Conway，1937 ~ 2020）不幸于新冠肺炎疫情中去世。他的研究兴趣涵盖组合游戏、群论等多个领域，在有限群分类、元胞自动机和组合游戏上做出了重要的贡献；他致力于数学科普，设计了曾风靡全球的“康威生命游戏”（Conway's Game of Life）。
今天，让我们来回顾他最著名的发明之一。
生命游戏的规则如下：
- 有一个正方形网格，每个格子中有一个细胞，细胞有两种状态：死亡或存活。每个细胞在下一刻的状态都由其现在的状态以及周围 8 个细胞的状态唯一确定。
- 当前细胞为存活状态时，如果它周围的存活细胞低于 2 个（不包含 2 个），该细胞变成死亡状态。
- 当前细胞为存活状态时，如果它周围有 2 个或 3 个存活细胞，该细胞保持原样。
- 当前细胞为存活状态时，如果它周围有超过 3 个存活细胞，该细胞变成死亡状态。
- 当前细胞为死亡状态时，当周围有 3 个存活细胞，该细胞变成存活状态，否则仍是死亡状态。
题目描述
由于计算机内存限制，我们无法模拟无限大的网格上的生命游戏，因此我们只考虑 $4\times 4$ 网格上的生命游戏，即认为网格外禁止细胞存活。
接下来你有 $Q$ 组询问，每次给你一个 $4\times 4$ 网格上的每个格子状态。问你 $T$ 个时刻之后网格上每个格子的状态。
输入格式
从标准输入读入数据。
第一行输入一个正整数 $Q$，表示询问组数。
接下来 $5Q$ 行，每 $5$ 行表示一组询问。
每组询问前 $4$ 行每行一个长为 $4$ 的 01 组成的字符串。表示这个网格上每个格子的细胞状态，其中 0 表示死亡，1 表示存活；接着一行一个正整数 $T$，表示接下来经过多少个时刻。
输出格式
输出到标准输出。
输出 $4Q$ 行，每 $4$ 行表示一组询问对应的答案。
每组询问的答案，每行一个长为 $4$ 的 01 组成的字符串。表示这个网格上每个格子的细胞状态，其中 0 表示死亡，1 表示存活。
样例
输入
1
0000
1100
0110
0000
3输出
0100
1010
1010
0100解释
经过一个时刻后，网格状态变为
0000 1110 1110 0000
再经过一个时刻后，网格状态变为
0100 1010 1010 0100
然后下一个状态会与该状态相同，也就是说接下来的时刻永远都会保持这一状态。因此从开始经过 3 个时刻后是该状态。
样例二
见下载目录下的 ex_2.in 与 ex_2.ans。
子任务
对于 $100\%$ 的数据，保证 $Q \le 10^{4}, T \le 10^{9}$
| 测试点 | $Q$ | $T$ |
|---|---|---|
| 1,2,3,4 | $= 10^{2}$ | $\le 10^{2}$ |
| 5,6,7 | $= 10^{3}$ | $\le 10^{3}$ |
| 8,9 | $= 10$ | $\le 10^{9}$ |
| 10 | $= 10^{4}$ |
时空限制：1s, 256MB