Master of copy and paste

Interview

Time limit2sMemory limit256 MB

Summary

Hanshin builds a target string by typing one character at a time or pasting a fixed clipboard string, and the task asks for the minimum total time.

Level: Easy3 of 10
Topics: Greedy, String matching
Solved: No attempts yet

Problem

Hanshin types slowly, so he does almost everything at school with copy and paste. Typing a character by hand costs 1 second, so typing $n$ characters costs $n$ seconds. Pasting the clipboard costs 1 second no matter how long its contents are.

The clipboard holds the string $p$ , and its contents never change. Starting from an empty screen, Hanshin repeats two moves, typing a single character or pasting the whole of $p$ , until the screen shows exactly the string $s$ . Both moves append to the end of what he has built so far. With "bana" on the clipboard, building "banana" takes 3 seconds: paste "bana", then type 'n' and 'a'.

Find the minimum time needed to build $s$ .

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 25$ ).

Each of the next $T$ lines contains two strings $s$ and $p$ separated by a single space. The length of $s$ is between 1 and 10,000, the length of $p$ is between 1 and 100, and both strings consist of lowercase English letters.

Output

For each test case, print on its own line the minimum time in whole seconds that Hanshin needs to build $s$ using $p$ .

Examples2

Example 1
Input
```
2
banana bana
asakusa sa
```
Expected output
```
3
5
```
Example 2
Input
```
3
abc abc
ab abcdef
abcdef xyz
```
Expected output
```
1
2
6
```