Server Time: Sun Aug 18, 2019 4:31 am
Welcome ( logout
1157 - LCS Revisited
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB

LCS means 'Longest Common Subsequence' that means two non-empty strings are given; the longest subsequence that are common. Subsequence means removing 0 or more characters from a string.

Now you are given two non-empty strings s and t, your task is to find the number of distinct LCS of s and t. Since the result can be very big, print the result modulo 1000007.

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case contains two lines, the first line is the string s and the second line is the string t. You may assume that the strings are non-empty and consist only of lowercase letters and the length of the each string is at most 1000.

Output

For each case, print the case number and the number of distinct LCS of s and t modulo 1000007.

Sample Input

Output for Sample Input

4

acbd

acbd

vnvn

vn

ab

ba

xyz

abc

Case 1: 1

Case 2: 1

Case 3: 2

Case 4: 1

 


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan