#2646 Typing

1 s   128 MB  

Description

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.

Input

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.

Output

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

Source

2015 ACM-ICPC Taiwan Online Programming Contest