알파벳 소문자로만 이루어진 문자열 S가 있다.

이 문자열을 두고 여러 번 질문이 주어진다.
각 질문은 하나의 알파벳 소문자 α와 두 정수 l, r로 이루어진다.

질문에 답하려면 문자열 S에서 l번째 문자부터 r번째 문자까지를 확인해야 한다.
이때 양 끝의 문자를 모두 포함하며, 문자열의 문자는 0번째부터 센다.

각 질문마다 해당 구간 안에 알파벳 α가 몇 번 나타나는지 구하는 프로그램을 작성하시오.

입력

첫 줄에 문자열 S가 주어진다.
문자열의 길이는 200,000자 이하이며 알파벳 소문자로만 구성되었다.

두 번째 줄에는 질문의 수 q가 주어진다.

세 번째 줄부터 q개의 줄에는 질문이 주어진다.
각 질문은 알파벳 소문자 αi와 정수 li, ri가 공백으로 구분되어 주어진다.

출력

각 질문마다 줄을 구분해 순서대로 답변한다.
i번째 줄에 S의 li번째 문자부터 ri번째 문자 사이에 αi가 나타나는 횟수를 출력한다.

제한

• 1 ≤ q ≤ 200,000
• 0 ≤ li ≤ ri < |S|

예제 입력 1

seungjaehwang
4
a 0 5
a 0 6
a 6 10
a 7 10

예제 출력 1

0
1
2
1