Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Xuejiejie loves strings most. In order to win the favor of her, a young man has two strings $X$, $Y$ to Xuejiejie. Xuejiejie has never seen such beautiful strings! These days, she is very happy. But Xuejiejie is missish so much, in order to cover up her happiness, she asks the young man a question. In face of Xuejiejie, the young man is flustered. So he asks you for help.

The question is that :

Define the $L$ as the length of the longest common subsequence of $X$ and $Y$.( The subsequence does not need to be continuous

in the string, and a string of length $L$ has $2^L$ subsequences containing the empty string ). Now Xuejiejie comes up with all subsequences of length $L$ of string $X$, she wants to know the number of subsequences which is also the subsequence of string $Y$.

The question is that :

Define the $L$ as the length of the longest common subsequence of $X$ and $Y$.( The subsequence does not need to be continuous

in the string, and a string of length $L$ has $2^L$ subsequences containing the empty string ). Now Xuejiejie comes up with all subsequences of length $L$ of string $X$, she wants to know the number of subsequences which is also the subsequence of string $Y$.

In the first line there is an integer $T$, indicates the number of test cases.

In each case:

The first line contains string $X$, a non-empty string consists of lowercase English letters.

The second line contains string $Y$, a non-empty string consists of lowercase English letters.

$1\leq |X|,|Y|\leq 1000$, $|X|$ means the length of $X$.

In each case:

The first line contains string $X$, a non-empty string consists of lowercase English letters.

The second line contains string $Y$, a non-empty string consists of lowercase English letters.

$1\leq |X|,|Y|\leq 1000$, $|X|$ means the length of $X$.

提交代码