Bạn được cho hai xâu kí tự ~s~ và ~t~ (chỉ gồm các chữ cái in hoa).

Nhiệm vụ của bạn hãy đếm số lượng xâu con ~a~ của ~s~ thỏa mãn đồng thời hai điều kiện:

• ~t~ là dãy con của ~a~
• Nghịch đảo của ~t~ là dãy con của ~a~

Xâu ~a~ được gọi là xâu con của ~b~ nếu ~a~ được tạo ra bằng cách không xóa hoặc xóa một số phần tử ở hai đầu của ~b~.

Xâu ~a~ được gọi là dãy con của ~b~ nếu ~a~ được tạo ra bằng cách không xóa hoặc xóa một số phần tử của ~b~ mà không thay đổi thứ tự của các phần tử còn lại.

Input

• Dòng đầu tiên chứa số nguyên ~T~ là số bộ test (~1 \le T \le 10~).
• Mỗi bộ test gồm 2 dòng chứa hai xâu ~s~ và ~t~ (~1 \le |t| \le 50~).

Output

• Với mỗi bộ test, in ra trên một dòng là số lượng xâu ~a~ thỏa mãn.

Samples

Input 1

2
ABABA
AB
ZZ
Z

Output 1

6
3

Scoring

• Subtask ~1~ (50% số điểm): ~1 \le |s| \le 100~
• Subtask ~2~ (50% số điểm): ~1 \le |s| \le 10^5~

Notes

Ở bộ test thứ nhất, có 6 cách chọn xâu con ~a~ thỏa mãn: ABABA, ABABA, ABABA, ABABA, ABABA và ABABA