Rafa always interested in string problem and playing with string when feel bored. One day he is trying to write all the string which is lexicographically larger than string s and lexicographically smaller than string t and the length of the strings are same as the length of s and t. The string s and t consist of lowercase English letters of same length. After a few moment he got tired and thinking to solve it with computer. As he is so tired he want you to write a program to find how many string exist for the given constrains.

Input

Input starts with the number of test cases T (T<=100). Each input contains two lines, the first line contains string s (1 ≤ |s| ≤ 100), consisting of lowercase English letters. Here, |s| denotes the length of the string.

The second line contains string t (|t| = |s|), consisting of lowercase English letters.

It is guaranteed that the lengths of strings s and t are the same and string s is lexicographically less than string t.

Output

Print the case number and the result. Since the result may be large you should print the result modulo 1,000,000,007. For better understand check the input and output given below.

Example

Input:
3
a
d
abcdefg
abcdefh
xy
yz

Output:
Case 1: 2
Case 2: 0
Case 3: 26

Problem Setter:

Md. Istiyak ahmed
Daffodil International University, Dhaka