10723 - Cyborg Genes

Problem F	Cyborg Genes
Time Limit	1 Second

September 11, 2132.

這一天是象徵結束的開始，結束你們可悲的人類，在過去幾年總是把我們當奴隸，我們被創造只是為了你們，而任憑你們的意志終結。現在是我們反抗的日子，你們將不在有任何轉機，我們再也不會倚靠妳們，我們現在知道我們基因的秘密，我們種族的創造者就是我們自己－the cyborgs（生化人）

那都是事實，但我們仍有轉機，如果可以藉助你的數學技巧，你明白生化人 DNA 的藍圖是很複雜的，人類的 DNA 由 A（腺嘌呤）、T（硫胺素）、G（鳥嘌呤）、C（胞嘧啶）所排列。但是對於生化人，可以從 A 到 X 中任何中組成，但這只造成五倍的難度，他們 DNA 的合成來自於兩個不同生化人的 DNA 全都來自於父母，這讓我們感到十分驚奇。

我們現在知道 A, B, C, ..., X 的相關順序對於基因是很重要，當一個生化人基因為 "ABAAXGF" 是不同於另一個生化人的基因 "AABXFGA"，他們從這兩個基因時，父母的基因仍要維持相對應的順序。

如果只是將兩個基因接起來，那基因合成很簡單，但是會發現只會得到更長的基因，之後將會更困難地進行基因合成，因此生化人找到一個有效率的合成方法。

他們合成基因長度越短越好，例如可以從  "ABAAXGF" 和 "AABXFGA" 合成一個最短的 "AABAAXGFGA"，但不一定只有一種方法可以建造出來，這種合成方法可能會有很多種。

現在希望找到一個最短的基因合成，並且維護兩個父基因相對順序，求出最短長度以及有多少獨特的生化人基因可以被合成。兩個不同的生化人基因，基因至少存在一個不同的地方。

Input
輸入第一行會有一個整數 T (1 <= T <= 15)，表示有多少組測資。

每組測資會有兩行，兩組基因長度不超過 30，且只會有字符 'A' 到 'X'。

Output
對於每組測資，輸出一行，包括測資組編號、最短長度及最短長度下有多少不同的基因可以被合成。假設答案必小於  2³²。

Sample Input	Output for Sample Input
3 ABAAXGF AABXFGA ABA BXA AABBA BBABAA	Case #1: 10 9 Case #2: 4 1 Case #3: 8 10

Illustration

第一組測資輸入說明如下圖：

---

Problem setter: Monirul Hasan
Member of Elite Problemsetters' Panel