最长公共子序列问题描述与实验目的：

序列Z=<B，C，D，B>是序列X=<A，B，C，B，D，A，B>的子序列，相应的递增下标序列为<2，3，5，7>。

一般地，给定一个序列X=<x1,x2,…,xm>，则另一个序列Z=<z1,z2,…,zk>是X的子序列，是指存在一个严格递增的下标序列〈i1,i2,…,ik〉使得对于所有j=1,2,…,k使Z中第j个元素zj与X中第ij个元素相同。

给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

你的任务是：给定2个序列X、Y，求X和Y的最长公共子序列Z。

输入样例

2

7 6

A B C B D A B

B D C A B A

8 9

b a a b a b a b

a b a b b a b b a



输出

Case 1

4 LCS(X,Y):B C B A

Case 2

6 LCS(X,Y):a b a b a b

-Longest common subsequence problem

Descr iption and Purpose:

Z = <B,C,D,B> sequence is the sequence X = <A,B,C,B,D,A,B> the sequence, the corresponding sequence of increasing subscr ipt <2,3,5,7 >.

In general, given a sequence X = <x1,x2,…,xm>, then another sequence Z = <z1,z2,…,zk> is a sub-sequence of X, is the existence of a strictly increasing sequence subscr ipt <i1,i2,…,ik> such that for all j = 1,2, ..., k so that the first j elements Z zj and X the same as the first element ij.

Given two sequences X and Y, when another sequence Z as X, Y promoter sequence is a sub sequence, said sequence of X and Y Z is the common subsequence.

Your task is: given two sequences X, Y, X and Y find the longest common subsequence Z.

Input sample

2

76

A B C B D A B

B D C A B A

89

b a a b a b a b

a b a b b a b b a



Output

Case 1

4 LCS (X, Y): B C B A

Case 2

6 LCS (X, Y): a b a b a b