Bajtek 正在参加《算法导论》课程。今天，他学习了解决文本模式匹配问题的有效算法。他已经实现了一个高效的程序，可以从输入中读取文本 $s$ 和模式 $t$（两者均由小写英文字母组成），并确定模式 $t$ 作为文本 $s$ 的子串出现的次数。

为了测试程序的正确性，Bajtek 生成了一个示例文本 $s$ 和模式 $t$。程序给出了正确的答案，但 Bajtek 对这个正确答案并不满意……他非常希望修改他的测试用例，使得模式出现的次数尽可能多。不幸的是，Bajtek 的文本编辑器在处理大文件时很吃力。它只允许对文本 $s$ 中的字母顺序进行任意更改，并且可以单独对模式 $t$ 中的字母顺序进行任意更改。

你能帮助 Bajtek 确定，如果他对其测试用例进行最优编辑，模式 $t$ 在文本 $s$ 中出现的最大次数吗？

输入格式

输入的第一行包含一个整数 $z$ ($1 \le z \le 100\,000$)，表示独立测试用例的数量。每个测试用例的描述占一行，包含两个由小写英文字母组成的单词 $s$ 和 $t$。

你可以假设 $1 \le |t| \le |s| \le 2\,000\,000$。此外，输入文件中所有单词的总长度不超过 $4\,000\,000$ 个字符。

输出格式

输出应包含 $z$ 行；第 $i$ 行应包含一个整数，表示在编辑 Bajtek 的第 $i$ 个测试用例后，模式在文本中出现的最大次数。

样例

输入 1

2
bajkaaall aal
abca cba

输出 1

2
1

说明 1

第一个样例的解释：Bajtek 可以将文本 $s$ 中的字母顺序更改为 balalajka，并将模式 $t$ 中的字母顺序更改为 ala。编辑后，该模式在文本中出现了两次。