D. Deliver the string
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

What's the meaning of "v" in "ctrl+v" ?

给定两个非空字符串$$$A$$$和$$$B$$$，同时你有一个空串$$$C$$$。

每次操作你可以选择字符串$$$A$$$的一个子串，并将这个子串加到字符串$$$C$$$的尾部(注意这个过程并不会改变字符串$$$A$$$)。

请问最少使用几次操作能使字符串$$$C$$$与字符串$$$B$$$相等。

Input

第一行一个整数$$$T$$$($$$1 \leq T \leq 2 \times 10^5$$$)表示数据组数。

接下来每组数据有 $$$2$$$ 行，第一行是字符串$$$A$$$,第二行是字符串$$$B$$$。

在同一数据点内，我们保证$$$\sum |A|, \sum|B| \leq 2 \times 10^5$$$。

输入数据保证一定能通过操作使字符串$$$C$$$与字符串$$$B$$$相等。

输入数据保证所有字符都是小写字母。

Output

输出$$$T$$$行，每行一个整数表示最少操作。

Example
Input
3
jzq
jzqjzq
abcd
dcbadcba
aabaaabaaaab
aabaaaaaba
Output
2
8
2
Note

对于第一组样例：连续两次把$$$A$$$串插入在$$$C$$$尾部即可。

对于第二组样例：依次插入"d","c","b","a","d","c","b","a"。

对于第三组样例：依次插入"aabaaaa","aba"。