폴리는 크래커를 원해

해적 사회에서는 모든 해적 선장이 반드시 애완동물을 한 마리 길러야 한다. 이 애완동물은 항상 선장의 곁(또는 어깨 위)에 있어야 하는데, 특히 선장의 악행을 꾸짖으러 온 정의로운 자들과 말다툼을 벌일 때 더욱 그렇다.

그리드비어드(Greedbeard)는 해적선 그레이트루터(Greatlooter)의 악명 높고 두려운 선장이다. 그의 애완동물은 역시 악명 높고 두려운 앵무새 폴리(Polly)이다. 앵무새답게 폴리는 주변에서 들리는 대화를 따라 하기를 좋아하지만, 그다지 잘하지는 못한다. 그래서 그리드비어드는 폴리가 사람의 말을 배우도록 직접 돕기로 했다.

폴리는 문장 전체를 따라 말할 수 있지만, 흔히 다음 세 가지 실수 중 하나 이상을 저지른다.

1. 단어의 순서를 뒤섞는다. 예를 들어 "polly wants a cracker" 대신 "polly cracker a wants"라고 말한다.
2. 일부 단어를 빠뜨린다. 예를 들어 "polly wants a cracker" 대신 "polly a cracker"라고 말한다.
3. 한 단어 안에서 글자를 넣거나, 빼거나, 바꾼다. 예를 들어 "polly wants a cracker" 대신 "polly wantsu a trackets"라고 말한다.

폴리는 한 문장에서 같은 원래 단어를 두 번 따라 하지 않으며, 선장은 폴리가 말하려던 원래 문장을 항상 알고 있다.

그리드비어드는 앞의 두 가지 실수(순서 뒤섞기, 단어 빠뜨리기)는 신경 쓰지 않는다. 그러나 한 단어 안에서 글자를 틀리는 것은 그를 몹시 화나게 한다. 폴리가 글자를 틀린 단어마다, 선장은 틀린 글자 수만큼 자기 점심에서 크래커를 하나씩 빼앗는다. 한 단어에 대해 빼앗는 크래커의 수는, 폴리가 실제로 말한 단어를 원래 말하려던 단어로 바꾸는 데 필요한 최소 편집 횟수와 같다. 한 번의 편집이란 글자 하나를 삽입하거나, 삭제하거나, 다른 글자로 바꾸는 것을 뜻한다.

말한 문장의 어떤 단어가 원래 문장의 어떤 단어에 대응하는지는 항상 분명하지는 않다. 그리드비어드는 편집 횟수의 총합이 최소가 되도록 말한 단어들을 원래 단어들에 대응시키며, 말한 각 단어는 서로 다른 원래 단어 하나에 대응된다.

예를 들어 원래 문장이 "polly wants a cracker"이고 폴리가 "polly crackets wantsu"라고 말했다면, 선장은 크래커 3개를 빼앗는다. "cracker"를 "crackets"로 틀린 것에 2개, "wants"에 글자를 하나 더한 것에 1개이다. "a"가 빠진 것이나 단어 순서가 뒤바뀐 것은 상관하지 않는다.

원래 문장과 폴리가 말한 문장이 주어질 때, 선장이 빼앗을 크래커의 총 개수를 구하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다.

• 첫째 줄: 폴리가 따라 하려는 원래 문장 ($1 \le \text{길이} \le 1000$)
• 둘째 줄: 폴리가 실제로 말한 문장 ($1 \le \text{길이} \le 1000$)

추가 조건:

• 원래 문장은 1개 이상 8개 이하의 단어로 이루어진다.
• 단어는 소문자 알파벳으로 이루어진 문자열이다. 단어들은 공백 하나로 구분되며, 앞뒤 공백이나 연속된 공백은 없다.
• 폴리는 단어를 새로 지어내지 않으므로, 말한 문장의 단어 수는 원래 문장의 단어 수를 넘지 않는다.

각 테스트 케이스마다, 선장이 빼앗을 크래커의 개수를 한 줄에 하나의 정수로 출력한다. 이는 말한 각 단어를 서로 다른 원래 단어 하나에 대응시키는 모든 방법 중에서 편집 횟수 총합의 최솟값이다.