Wielka Przesmycka 2011 Eternal

In team programming contests, teams solve problems denoted with digits and uppercase and lowercase letters. It is thus easy to calculate that there are 2 * 26 + 10 = 62 problems. During the competition, every team submits various problems for verification. Therefore, the sequence of a team's submissions is a sequence of digits and uppercase and lowercase letters, where characters may be repeated.

The coach of one of the teams, a certain Professor M., recently came up with a crazy idea to boost the performance of his team: he devised a minimum and maximum plan for the team. The minimum plan is a sequence of submissions that the team has to make in order not to disappoint Professor M. In between the submissions belonging to the minimum plan, the team is allowed to make other submissions. However, it needs to remember not to exceed the maximum plan, meaning that the sequence of submissions needs to be a subsequence of the maximum plan. Otherwise, the professor will also be disappointed. We will call a sequence of submissions admissible if it doesn't disappoint Professor M. For example, if the minimum plan is BBAb and the maximum plan is CBBAbAb, then some admissible sequences are BBAb, CBBAbb and BBbAb.

The team is wondering how many admissible sequences of submissions there are. Help them!

Multiple test cases

The first line of the input contains Z ≤ 20 - the number of test cases. Z descriptions of single test cases follow.

Single test case

The first line contains the maximum plan, the second line the minimum plan. The plans are nonempty and consist of digits and uppercase and lowercase letters. The lines contain no spaces.

Bounds

Basic: each plan has length at most 200.
Professional: each plan has length at most 2000.

Output

Print a line containing one number X mod (10⁹ + 7), where X is the number of admissible sequences of submissions.

Sample input

2
abc
b
WielkaPrzesmycka2011
Przesmycka

Sample output

4
768