Por Joel Uchoa, IFCE Brazil
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.
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).
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|