Cho xâu \(S\) có độ dài \(N\) gồm các ký tự chữ cái tiếng Anh thường. Cho Q truy vấn. Mỗi truy vấn có dạng \((a_i,b_i)\), trong đó \(a_i\) và \(b_i\) là các ký tự từ bảng chữ cái tiếng Anh thường.

Yêu cầu: Với mỗi truy vấn \((a_i,b_i)\), In ra số lượng chuỗi con gồm các phần tử liên tiếp nhau của \(S\), mà ký tự đầu tiên là \(a_i\) và ký tự cuối cùng là \(b_i\).

Input

• Dòng đầu tiên chứa xâu \(s(1≤|s|≤10^5)\).

• Dòng thứ hai chứa số nguyên \(Q(1 ≤ Q ≤ 10^5)\), số lượng truy vấn.

• Mỗi một trong số \(Q\) dòng tiếp theo chứa hai ký tự \(a_i\) và \(b_i\), cách nhau bằng một khoảng trắng.

Output

• Đối với mỗi truy vấn, in ra số lượng xâu con của \(S\), mà ký tự đầu tiên là đầu tiên là \(a_i\) và ký tự cuối cùng là \(b_i\).

Sample Input

abacaba
2
a b
b b

Sample Output

4
3