Description

一卷桌布，里面包含一些图案，小明家里有一块桌布，上面也包含一些图案。

对于给定的一卷桌布，小明想要计算一下能从这卷桌布里剪出多少块和自己家那块完全相同的桌布。

Input Format

输入第一行包含一个整数 $T$ ($1 \le T \le 3000$)，表示数据组数。

接下来 $T$ 行，每行包含两个以空格分开的字符串，分别表示一卷桌布和小明家里的桌布图案。这些图案都是用 ASCII 字符表示的，每个字符串长度不超过 1000。

Output Format

对于每组数据，输出一行一个整数，表示能从一卷桌布中剪出的桌布数量。

2
abcde a3
aaaaaa aa

0
3