請注意本題不同尋常的時間限制。

生物學家矮人最近在弗羅茨瓦夫大學的民俗遺傳學領域取得了突破性發現。經過多年的研究，他成功對居住在該市的三種不同物種的 DNA 進行了定序：矮人（他自己的種族）、地精（魔法森林的居民）以及青銅人（弗羅茨瓦夫街頭傳說中的青銅雕像族）。

每個 DNA 序列都表示為一個二進位字串，其中 0 代表隱性遺傳標記，1 代表顯性遺傳標記。他的目標是找出這三個物種共有的遺傳標記的最長共同子序列（LCS）——這將揭示他們共同的演化祖先，並解釋為什麼他們最終都來到了弗羅茨瓦夫！然而，計算三個序列的精確 LCS 在計算上非常昂貴，且矮人的研究經費即將耗盡。他不需要完美的精確度；他只需要找到一個整數 $x$，使得 3-LCS 的真實長度落在區間 $[x, 2x]$ 內。換句話說，一個 $2$-近似值就足夠了。

這個近似值對於他的研究論文來說已經足夠好，並且仍然能為弗羅茨瓦夫魔法居民的共同遺傳遺產提供有價值的見解。你能幫矮人找到這樣的一個近似值嗎？

輸入格式

輸入的第一行包含數字 $T$，代表測試資料的組數。

每組測試資料包含四行。第一行包含一個整數 $N$，表示 DNA 序列的長度。接下來的三行包含長度為 $N$ 的二進位字串，分別代表矮人、地精和青銅人的 DNA 序列。

輸出格式

對於每組測試資料，輸出一個整數 $x$，使得這三個 DNA 序列的最長共同子序列的長度落在區間 $[x, 2x]$ 內。

資料範圍

$1 \le T \le 10$，$1 \le N \le 3000$，每個字串僅由數字 0 和 1 組成。

範例

輸入格式 1

2
4
0010
0110
0101
2
10
00
01

輸出格式 1

2
1

說明

在第一個範例中，最佳的 LCS 為 010，因此其長度為 $3$。因此答案 $2$ 也是正確的。