복붙의 달인

면접 대비

시간 제한2초메모리 제한256 MB

요약

고정된 클립보드 문자열을 붙여넣거나 한 글자씩 직접 입력해 목표 문자열을 만드는 데 드는 최소 시간을 구합니다.

난이도: 쉬움10점 중 3점
유형: 그리디, 문자열 매칭
정답자: 아직 제출이 없습니다

문제

한신이는 타이핑이 느려서 학교 일을 대부분 복사와 붙여넣기로 처리한다. 문자를 직접 입력하면 한 글자에 1초가 걸리므로 $n$ 개의 문자를 입력하면 $n$ 초가 걸린다. 반면 클립보드에 담긴 문자열은 길이가 얼마든 붙여넣기 한 번에 1초면 끝난다.

클립보드에는 문자열 $p$ 가 들어 있고, 내용은 끝까지 바뀌지 않는다. 한신이는 빈 화면에서 시작해 문자를 하나 입력하거나 $p$ 를 통째로 붙여넣는 동작을 되풀이해서 문자열 $s$ 를 정확히 완성하려고 한다. 두 동작 모두 지금까지 만든 문자열 뒤에 이어 붙는다. 클립보드에 "bana"가 있는 상태에서 "banana"를 만든다면 "bana"를 붙여넣고 'n'과 'a'를 입력해서 3초가 걸린다.

$s$ 를 완성하는 데 걸리는 최소 시간을 구하라.

입력

첫 줄에 테스트케이스의 개수 $T$ 가 주어진다 ( $1 \le T \le 25$ ).

이어지는 $T$ 개의 줄에는 각각 문자열 $s$ 와 $p$ 가 공백 하나로 구분되어 주어진다. $s$ 의 길이는 1 이상 10,000 이하, $p$ 의 길이는 1 이상 100 이하이며, 두 문자열은 알파벳 소문자로만 이루어진다.

출력

각 테스트케이스마다 한신이가 $p$ 를 이용해 $s$ 를 완성하는 데 걸리는 최소 시간을 초 단위 정수로 한 줄에 하나씩 출력한다.

예제2

예제 1
입력
```
2
banana bana
asakusa sa
```
예상 출력
```
3
5
```
예제 2
입력
```
3
abc abc
ab abcdef
abcdef xyz
```
예상 출력
```
1
2
6
```