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.