題目背景
著名數學家約翰·康威（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
1
0000
1100
0110
0000
3輸出 1
0100
1010
1010
0100說明 1
經過一個時刻後，網格狀態變為
0000 1110 1110 0000
再經過一個時刻後，網格狀態變為
0100 1010 1010 0100
然後下一個狀態會與該狀態相同，也就是說接下來的時刻永遠都會保持這一狀態。因此從開始經過 3 個時刻後是該狀態。
輸入 2
見下載目錄下的 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}$ |