ODWS - One day with string

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


Added by:shuvo karmakar
Date:2015-04-03
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY

hide comments
2015-04-04 03:00:30 eightnoteight
nice problem. but weak test cases because the answer for s="z" and t="a" is 0 but one of my solution which gives 999999981got ac

Last edit: 2015-04-04 03:00:44
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.