E. Rearrange

No Submission Yet

Problem Statement

Health class ultimately proved to be too disturbing. Dominos made Tiger think of Domino's the restaurant, and then Domino's greasy calorically dense pizzas, which went against the healthy eating nutrition pyramid. So Tiger decided to play with strings instead.

In particular, he has a string \(s\) and a favorite string \(t\). Both \(s\) and \(t\) consist of lowercase Latin letters. He wants to rearrange the characters of \(s\) to form a new string \(p\). The way Tiger rearranges the characters of \(s\) to form \(p\) is by iterating over the characters of \(s\) from left to right and adding each character to either the front or the back of \(p\) (which is initially empty).

He wants you to tell him the maximum number of times \(t\) can appear as a substring in \(p\). You will have to answer \(q\) independent test cases.

Additional Notes

Time Limit:
C++: 2.5 seconds
Java, Python: 5 seconds
Memory Limit: 256mb


\((1 \leq q \leq 100)\)
\((1 \leq |t| \leq |s| \leq 200)\)
It is guaranteed that the sum of \(|s|\) over all test cases does not exceed \(200\).

Input Format

The first line has a single integer \(q\) — the number of independent test cases.
The first line of each test case has the string \(s\) .
The second line of each test case has the string \(t\) .

Output Format

For each test case, output a single integer — the maximum number of times \(t\) can appear in \(p\) as a substring.

Sample Input


Sample Output


Sample Explanation

For the second testcase, the construction is bcaebca, in which bca appears twice.

Credit: Eggag

Contact Us
LIT Discord Server