2 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 |
---|---|

2 banana bana asakusa sa | 3 5 |