Your friend is a biologist. He has just sequenced a DNA and wants to know about contribution of different genes in that DNA. Both Gene and DNA can be represented by a sequence of letters or strings. Given the sequence of a DNA D and a Gene G; your friend uses following method to calculate the contribution.

1. Generate a list P of proper non-empty prefixes of G and another S of proper non-empty suffixes of G [1]. Additionally let the L is list of all strings that is concatenation of a prefix and a suffix. So if G = ACCT then P = A, AC, ACC and S = T, CT, CCT and L = AT, ACT, ACCT, ACT, ACCT, ACCCT, ACCT, ACCCT, ACCCCT. If |G| = n then it is obvious that size of L is (n - 1)².
2. For each element of L, count number of times it occurs as substring in D. Contribution of Gene G in DNA D is total of these values. For example if D = ACTACCTACCCCT then:

As this process is very clumsy he wants to automate this process. As he is not a programmer, he needs your help. He will be very grateful if you kindly write him a program which will read the sequence of the DNA and the Gene, and will calculate contribution of the Gene in the DNA.

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

Each case contains two lines. The first line contains a string denoting the sequence of DNA, and the second line contains another string denoting the Gene. The length of each string is less than 50000 and consists of only A, C, T and G.

For each case, print the case number and the contribution, as described above.

1. Proper prefix (suffix) of a string S is a prefix (suffix) of length smaller than |S|. Here |S| denotes length of S.
2. Dataset is huge, use faster I/O methods.