7/9這天，菜雞在水中發現潛藏著一個傳染性極高的病毒，命名為 79-retawdivoc，但當菜雞要分析病毒時，卻發現病毒已經有很多種突變了，他想透過DNA序列分析各個病毒株的相似性，但病毒很狡猾，突變的過程中會在DNA中塞入很多不相關的基因編碼。菜雞發現，透過分別刪除兩個DNA的一些編碼，產生出完全相同的序列，在所有相同子序列的可能性中，最長子序列的長度即為那兩個DNA的相似度，這個資訊可以加快研發解藥的速度。
例如：兩個DNA序列ATCGGCGC、AGGGCTCT，共同的子序列可以是ATC、GGCC、TC、AGGCC、AGGGC等等，可以發現最長的子序列長度是5，這就是他們的相似度。
時間就是金錢，菜雞想要很貪心的一次分析多個DNA，所以他一次選出好幾個DNA，找出他們的最長共同子序列來判斷他們有多相近，你能幫幫菜雞嗎？
每筆測資只有一筆輸入
第一行輸入 $N$，代表字串的數量
接下來有 $N$ 行，每行包含一個由A、T、C、G組成的字串$S_i$
輸出一個整數，代表這組DNA的相似度。
3 ATTACG TACGAG ATACCG
4
20% $N = 2$
100% $1 \le N \le 7$, $1 \le len(S_i) \le 9$
範例輸入中，最長共同子序列為TACG。
注意：
這個病毒可能會經由網路與電力傳染，所以大家可以好好在家裡打 DDJ Regular Contest ，不要去外面與 COVIx-x9 混合，如果混合了可能突變更危險的病毒，如果要出門也要戴口罩，勤洗手喔。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||