Ký tự đầu cuối

Trong một buổi họp về chính sách mới, FullHouse Dev được giao nhiệm vụ phân tích các văn bản chính trị. Để đơn giản hóa việc này, họ cần phát triển một công cụ để đếm số lượng đoạn văn bản có ký tự đầu và cuối theo yêu cầu.

Bài toán

FullHouse Dev nhận được một chuỗi \(S\) và \(Q\) truy vấn. Mỗi truy vấn gồm hai ký tự \(x\) và \(y\). Nhiệm vụ của họ là đếm số lượng chuỗi con của \(S\) mà có ký tự đầu tiên là \(x\) và ký tự cuối cùng là \(y\). Hai chuỗi con \(S[i...j]\) và \(S[k...l]\) được coi là khác nhau nếu cặp \((i,j)\) khác với \((k,l)\).

INPUT FORMAT:

• Dòng đầu tiên chứa chuỗi \(S\)
• Dòng thứ hai chứa số nguyên \(Q\) - số lượng truy vấn
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai ký tự \(x\) và \(y\) cách nhau bởi dấu cách

OUTPUT FORMAT:

• Với mỗi truy vấn, in ra số lượng chuỗi con của \(S\) thỏa mãn yêu cầu

Ràng buộc:

• Chuỗi \(S\) chỉ chứa các ký tự chữ cái tiếng Anh viết thường
• \(1 \leq |S| \leq 10^5\)
• \(1 \leq Q \leq 10^5\)

Ví dụ

INPUT

abacaba
2
a b
b b

OUTPUT

4
3

Giải thích

• Ở truy vấn đầu tiên, các chuỗi con bắt đầu bằng 'a' và kết thúc bằng 'b' là: ab (từ vị trí 1 đến 2), abacab (từ 1 đến 6), acab (từ 3 đến 6), ab (từ 5 đến 6).
• Ở truy vấn thứ hai, các chuỗi con bắt đầu và kết thúc bằng 'b' là: b (vị trí 2), b (vị trí 6), bacab (từ 2 đến 6).