Viết một hàm đếm số lần xuất hiện của chuỗi ~s1~ trong chuỗi ~s2~. Sau đó, nhập vào một số nguyên ~m~ và danh sách ~m~ cặp chuỗi ~(s1, s2)~, sử dụng hàm vừa viết để đếm số lần xuất hiện của ~s1~ trong ~s2~.

Input

• Dòng đầu chứa một số nguyên ~m~ ~(1 \leq m \leq 100)~.
• ~m \times 2~ dòng tiếp theo:
  
  • Dòng trên chứa chuỗi ~s1~.
  • Dòng dưới chứa chuỗi ~s2~.
• Độ dài mỗi chuỗi không quá 100 ký tự.

Output

• In ra số lần chuỗi ~s1~ xuất hiện trong chuỗi ~s2~ cho từng cặp chuỗi đã nhập, mỗi số một dòng.

Ví dụ

Input 1

2
An
Tran Phi An Binh An
a
Tien Giang

Output 1

2
1

Input 2

3
he
hello world
test
this is a test test
abc
abcabcabc

Output 2

1
2
3

📌📌 Link thảo luận trên Facebook tại đây