Sắp tới sẽ diễn ra cuộc thi IGPT – một cuộc thi giải thuật đặc biệt dành cho Robot.

Với vai trò là người phụ trách kiểm tra thí sinh, \(HK\) đang băn khoăn không biết làm cách nào để phân biệt giữa con người và Robot. Sau một hồi suy nghĩ, cậu chợt nảy ra một bài kiểm tra thú vị:

Đề bài đưa ra hai đoạn mã \(a\) và \(b\), là hai xâu ký tự chỉ gồm các chữ cái viết thường.

Để hiểu rõ yêu cầu, ta cần biết hai khái niệm quan trọng sau:

• Một subsequence của một xâu là xâu có thể thu được bằng cách xóa đi một số (hoặc không xóa ký tự nào) trong xâu gốc, nhưng vẫn giữ nguyên thứ tự của các ký tự còn lại.
• Một substring của một xâu là một đoạn ký tự liên tiếp nhau trong xâu đó.

Ví dụ với xâu igpt:

• i, g, p, t, ig, ip, it, gp, gt, pt, igp, igt, ipt, gpt và igpt là các subsequence.
• i, g, p, t, ig, gp, pt, igp, gpt và igpt là các substring.

Nhiệm vụ của thí sinh là chứng minh mình thực sự là Robot bằng cách tìm ra độ dài nhỏ nhất của một xâu sao cho xâu đó chứa \(a\) như là một substring và chứa \(b\) như là một subsequence.

Đầu vào

Dòng đầu tiên chứa số nguyên \(T\) là số lượng testcase. \((1 \le T \le 10^3)\)

Dòng đầu tiên ở mỗi testcase chứa xâu \(a\) \((1 \le |a| \le 100)\), chỉ chứa các ký tự là chữ cái viết thường.

Dòng thứ hai ở mỗi testcase chứa xâu \(b\) \((1 \le |b| \le 100)\), chỉ chứa các ký tự là chữ cái viết thường.

Đầu ra

Ở mỗi testcase, in ra một số nguyên duy nhất là độ dài nhỏ nhất của xâu sao cho xâu đó chứa \(a\) như là một substring và chứa \(b\) như là một subsequence.

Ví dụ

Đầu vào

5
aba
cb
er
cf
mmm
mmm
contest
test
cde
abcefg

Đầu ra

4
4
3
7
7

Giải thích

Trong ví dụ thứ nhất, xâu thỏa mãn có thể là caba.

Trong ví dụ thứ hai, xâu thỏa mãn có thể là ercf.

Trong ví dụ thứ ba, xâu thỏa mãn có thể là mmm.

Trong ví dụ thứ tư, xâu thỏa mãn có thể là contest.

Trong ví dụ thứ năm, xâu thỏa mãn có thể là abcdefg.