Bạn được cho 2 xâu \(s\) và \(t\). Trong mỗi bước, bạn có thể xóa đi ký tự đầu tiên của 1 trong 2 chuỗi trên. Ví dụ:

• Xóa ký tự đầu tiên của where, trở thành xâu here.
• Xóa ký tự đầu tiên của a, trở thành xâu rỗng .

Yêu cầu: Bạn được yêu cầu sử dụng các bước trên để hai xâu \(s\) và \(t\) giống nhau. Viết chương trình đếm số bước ít nhất để làm được điều này.

Input

• Dòng đầu ghi \(t\) \((t\le 100)\) - số câu hỏi.
• \(t\) block tiếp theo, mỗi block gồm 2 dòng: một dòng chứa xâu \(s\), một dòng chứa xâu \(t\). Độ dài của cả 2 xâu đều không vượt quá \(10^5\).

Output

• Ứng với mỗi câu hỏi, in ra kết quả cần tìm.

Example

4
test
west
lqdoj
ttuoj
test
yes
b
ab

2
6
7
1