URI Online Judge | 2220
# Helping Gust-Avô

**Timelimit: 1**

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 **B ^{i}**
as a sequence where each letter of

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

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**|≤10^{5})
and the second line has a sequence **B** of letter (|**B**|≤10^{4}).

For each instance in the input, your must print a line with the
maximum integer **i**, such that **B ^{i}**
is a subsequence of

Input sample | Output sample |

4 |
1 |