You are given a string S of length N and there are Q queries. In each query, you are provided with 2 integers L and R. You need to find the number of distinct characters present in the range L to R.

Input :

• First line of Input contains N , length of string S.
• Second line of input contains string S containing lowercase alphabets only.
• Third line of Input contains Q , number of queries
• Each following Q lines contains 2 integers , L and R .

Output :

For each query , output number of distinct characters in newline .

Constraints :

• \( 1 \le N \le 10^{5} \)
• \( 1 \le Q \le 10^{5} \)
• \( 1 \le L \le R \le N \)