#P1063. 爱情小测验

爱情小测验

题目描述

雯君正在看一本时尚杂志,正如大家所熟知的一样,杂志里面都有很多心理测验(说是心理测验,大多数都是爱情指数测验,通过一系列稀奇古怪的指标来判断一男一女是否心有灵犀,测试两人是否默契,等等)。这些心理测验,雯君平时看的很多,也没怎么在意,反正在她心里,卿爷就是她的全部。但是正当她准备扔下手中的书跟卿爷一起去图书馆的时候,发现最后一个测验里面很多字符串,作为软件专业的她对此产生了强烈的兴趣,虽然说卿爷就是她的全部,但是她就是喜欢一次又一次地把时间花在这种小测验上。

“请你和你的情侣分别在两张不同的小纸条上写上两个世界上只有自己知道的字符串。写完以后,两人含情对视 10 秒(有必要吗?!),再同时打开手中的小纸条,接下来就是见证奇迹的时刻!

如果你写下的字符串的前缀与你的情侣写下的字符串的前缀反序相等,那么恭喜你们,你们已经是可以写出牛郎织女串的情侣了!接下来,为了更好的量化你们的牛郎织女程度,我们定义,你写下来的字符串长度为 xx 的前缀与你情侣写下来的字符串长度 xx 的前缀反序相等,那么你们的牛郎织女指数为 xx。如果你们的牛郎织女指数在 0-10,那么,@!)(&%!)#5”

后面的已经不重要了,雯君当然希望自己跟卿爷的牛郎织女指数越大越好。于是便马上拉着原本准备去图书馆的卿爷就地开始做起来。一晃 2 个小时过去了,卿爷和雯君写下了 100 多张小纸条(卿爷很无奈,但是如果不跟着一起写,后果很严重……)写完以后,卿爷已经昏厥过去,只有雯君还在小鹿撞怀的期待着见证奇迹的时刻。不过突然发现,由于刚刚被爱情冲昏了头脑,一口气写了 100 多张不说,每一张小纸条上都是密密麻麻的字符串。这得怎么知道每一张纸条的牛郎织女指数是多少呀,雯君就郁闷了,这时候不幸的你恰好路过准备前往校内程序设计大赛的赛场,雯君灵机一动,马上拉住你,怜香惜玉的你经不住雯君的苦苦哀求于是就答应了……(这题都没做出来,真不好意思去参加比赛了……)

输入格式

第一行为一个整数 TTT100T \leq 100),表示有 TT 组测试数据。接下来依次是各组测试数据的内容。每组测试数据格式如下:每一组数据包含两个字符串 AA, BB。(字符串 AA, BB 仅由 A..Za..z 组成,并且由一个空格隔开)。输入数据不会超过 100 组,字符串的长度不会超过 100000。

输出格式

对于每一组数据:一个正整数(表示对应两个字符串的最大牛郎织女指数)。

样例输入

1
abdaegg adbaggg

样例输出

提示

对于样例输入,这两个字符串牛郎织女指数为 1 的前缀有 a,牛郎织女指数为 4 的前缀有 abda