Ta gọi xâu \(R\) là xâu con của xâu \(S\) nếu ta có thể thu được xâu \(R\) bằng cách xoá đi một vài kí tự của xâu \(S\) và giữ nguyên thứ tự các kí tự còn lại.

Xâu \(C\) được gọi là xâu con chung của hai xâu \(A\) và \(B\) nếu \(C\) là xâu con của \(A\) và \(C\) là xâu con của \(B\). Đếm số lượng xâu con chung của hai xâu \(A\) và \(B\).

Input

• Dòng thứ nhất chứa số nguyên dương duy nhất là số bộ test \(T\) \((T \leq 40)\).
• Mỗi test gồm \(2\) dòng, mỗi dòng chứa một xâu gồm các kí tự trong 'a' đến 'z' viết liền nhau, giới hạn độ dài không quá \(10^3\).

Output

• Ghi ra \(T\) dòng, mỗi dòng là kết quả tương ứng cho một test là số xâu con chung. Vì kết quả có thể rất lớn nên chỉ in kết quả khi lấy dư cho \(20071008\).

Example

1
abc
ab 

3