Problem : 189 - ABC聚餐

Problem Statistics

Solved Member: 5　　Submission: 59　　User Tried: 14

Statement:

hh參加了一個有趣的下午茶聚會，那是一個有趣的聚會。

他們在一家名為東加衣吃下午茶，東加衣的食品提供是經由兩條迴轉道出來的!每條迴轉道只有一個出口與一個入口，一個食物只會出現在你眼前一次，錯過就無法在得到他。在兩條迴轉道上，有著來自東京的蘋果(Apple), 加勒比海的香蕉(Banana), 以及衣索比亞的咖啡(Coffee)。

在神祕的龍使傳說下，Double Eat是比7122(某種宗教儀式)還爽的事，也就是同時吃兩個蘋果或兩根香蕉或兩杯咖啡。但如果這兩個食品來自同一個地方，那吃起來味道就一樣了，所以有一個嚴苛的條件是他們必須來自不同地方(也就是兩條迴轉道各提供一個)。

hh透過神秘方法得到了兩條迴轉道依序出口的食品，所謂好馬不吃回頭草，兔子不吃窩邊草，一種食物過了就不再回頭，hh也無法再吃到。所以hh很想預先知道自己可以吃到幾次Double Eat。

我們以A,B,C代替三種食物，給你兩個由A,B,C組成的序列，代表兩個出口線出來的食物順序，問問hh可以吃到幾次Double Eat。

為了化簡問題，hh決定吃了B後便不再吃A，吃了C後便不再吃A與B，這樣應該有把問題化簡吧? (炸飛

簡單的說，現在給你兩個由ABC所組成的字串，你要找一個最長長度的字串屬於兩個字串的共同子序列(不一定要連續)，且是由A^*B^*C^*所構成。

其中A^*表示由不定個數的A所組成的字串(可以是空字串)。

Input:Output:

第一行為數字T，表示有T組測試資料。
每組測試資料有兩行由A,B,C所組成的字串，每個字串長度不超過200000，分別表示兩條出口線出口食物順序。

對於每一筆測試資料，請輸出在化簡問題後，hh能得到幾次Double Eat!

Sample Input:Sample Output:

3
AABCABCB
AABCABCB
ABC
AAAAA
ABABC
ABBCCA

5
1
4

HINT:

後來hh才發現，兩個出口線的食物來自同一個廚房阿！故hh無法得到Double Eat的爽感。

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1500ms	65536kb	10
8	1500ms	65536kb	10
9	1700ms	65536kb	10
10	1700ms	65536kb	10