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