Your friend is a biologist doing research on the structure of DNA. He wants to investigate how much a certain feature depends on the number of occurrences of the gene that causes it in the DNA of a person.

For this purpose he needs your help. You need to write a program that will take a part of DNA sequence, and a pattern. Your program needs to calculate how many times the pattern appears as a subsequence of the DNA sequence.

Input

In the first line your program reads T, the number of test cases.

Every test consists of two lines. First with the DNA sequence and second with the pattern.

Output

For every test output a single number, the total number of occurrences (as a subsequence) of the pattern in the sequence.

Example

Input:
3
ACGTACGT 
AT
AAAAA
AA
CGT
A

Output:
3
10
0