喵喵的IDE

Time Limit: 8000/4000MS (Java/Others) Memory Limit: 512000/256000KB (Java/Others)

Problem Description

喵喵有一个神奇的IDE,这个IDE自带一个cache,还有一个当前编辑区editarea,初始的时候这个 cache 中有一个字符串 cachebegin

喵喵想打按照顺序打N个字符串 x,她可以进行三种操作。

打之前 editarea 为空
1、从cache中拿出一个字符串 B直接赋值给editarea , editarea = B.(如果不拿那么不计入操作数)
2、如果editarea里面有字符,那wuyiqi可以删除掉editarea中最后一个字符。(删光了之后就不能删除啦!)
3、喵喵可以在editarea末尾插入一个任意字符。
如果editarea的字符串恰好与她要打的第i个字符串相同,那么她就完成了这次打印,并且这个字符串自动加入cache(cache中可能出现重复字符串),然后editarea自动清空。那么喵喵就会自动进入下一个字符串的打印阶段。
她想问,对于每次字符串输出,最少需要多少次操作。
1 ≤ N ≤ 105 , 字符串长度总和 ∑(Ai) <106 , cache_begin 长度< 100

Input

第一行一个整数T,代表数据组数。

对于每组数据第一行一个整数 N 代表要打印的字符串个数,还有一个字符串cachebegin

以下N 行每行一个字符串 Ai

A和 cachebegin 都只包含小写字母

Output

对于每组测试数据输出N个数。

Sample Input

1
3 a
a
ab
abc

Sample Output

1
2
2

Hint

一开始cache中为{"a"}
第一次操作直接拿出来{"a"}就好了

现在cache为{"a","a"}
拿出来"a",加入b,两次操作。

现在cache为{"a" , "a" , "ab"}
拿出来"ab",加入c。两次操作

Source

Dshawn & zhanyl

Manager

Information
Solved Number128
Submit Number793
Problem Tags
strings
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel