#2646 Typing

1 s   128 MB  


Cathy’s typing speed is not fast, however, it is very steady. She strokes the keyboard exact once
per second, and she always presses the keys correctly. Without interfering, Cathy has to spend
$n$ seconds to type a string s of $n$ characters. In order to reduce the time spent for typing, Cathy
copied a string $p$ to the clipboard. Therefore, she can use the “paste” function to input many
characters. Assume that pasting $p$ also takes only one keyboard stroke for Cathy. If Cathy
copied bana before typing banana, then Cathy can finish it in 3 seconds: pasting bana, then
pressing n, then pressing a. Please write a program to compute the minimum time required for
Cathy to type a string $s$ when she copied $p$ to the clipboard.


The first line of the input contains an integer $T$, $T \leq 25$, indicating the number of test cases.
Each test case has exactly one line containing two strings $s$ and $p$ separated by blanks. Cathy
is going to type $s$ with $p$ copied to the clipboard. The length of $s$ is at most 10000, and the
length of $p$ is at most 100.


For each test case, output the minimum time (in seconds) for Cathy to type $s$ with $p$ copied to
the clipboard.

Sample Input

Sample Output

banana bana
asakusa sa


2015 ACM-ICPC Taiwan Online Programming Contest