Time Limit: 2s Memory Limit: 256MB

题目描述

前缀自动机作为一种入门级数据结构,常常被用于字符串入门的教学中。由于日程限制,这种方便又好用的数据结构并未在预备队课程中讲授,因此在这里补充一道模(签)板(到)题,题意如下:

给定一组字符串\(S\)与\(P\),求\(P\)的前缀中,是\(S\)的子串的前缀中最长的长度是多少。 例如:\(S=aabbcc\),\(P=abc\),则最长符合条件的前缀是\(ab\),它的长度是\(2\),因此输出\(2\)。

输入格式

第一行是一个正整数\(T\)\((1\le T \le 5)\),表示测试数据组数。 接下来\(T\)组数据,每组第一行为\(S\),第二行为\(P\)。

数据保证\(S\)与\(P\)的长度不超过\(10^5\),且只包含小写字母。

输出格式

对于每组数据,输出一行,包含一个数,表示可以符合条件的最长前缀的长度。

样例输入

1
aabbcc
abc
    

样例输出

2