請注意呢題唔尋常嘅時間限制。

生物學家矮人最近喺弗羅茨瓦夫大學嘅民俗遺傳學領域取得咗突破性發現。經過多年嘅研究，佢成功對居住喺呢個城市嘅三個唔同物種嘅 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$ 亦係正確嘅。