URI Online Judge | 2220

Helping Gust-Avô

Por Joel Uchoa, IFCE BR Brazil

Timelimit: 1

K-rina is a young pokemon master and she likes help ancient pokemons. In her's last hunting, she has capture a old and stutterer writer pokemon called Gust-Avô. Because his stuttering, when Gust-Avô writes a word, sometimes, he repeats or add some letters from/to the word. K-rina wants help it interpreting it's texts. To that she needs solve the problem described below.

Given A and B two sequences os letter, we say B is a subsequence of A if we can find all letter of B into A in the same order (not necessarily adjacent). For example, abc is a subsequence of xaywbzc, instead that, xyz isn't subsequence of xabzcy.

Given a sequence B, we define Bi as a sequence where each letter of B is repeated i times. For example, if B=xyzzx, then B3=xxxyyyzzzzzzxxx.

To help K-rina and Gust-Avô, your task is: Given two sequences A and B, find the maximum value to i, such that Bi is a subsequence of A.

Input

The input consists of many instances of the problem. The first line contains just an integer T (1 ≤ T ≤ 20) that represents the number of instances.

Each instance is composed by two lines. The first line has a sequence A of letters (|A|≤105) and the second line has a sequence B of letter (|B|≤104).

Output

For each instance in the input, your must print a line with the maximum integer i, such that Bi is a subsequence of A. In the case of B isn't subsequence of A, prints 0 (zero).

Input sample Output sample

4
qwer
qr
qweqwewseerfgr
qr
aaaaaaaaa
a
qwer
asdf

1
2
9
0