Problem10991--K串

10991: K串

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

ZZT 得到了一个字符串 $S$ 以及一个整数 $K$。

WZH 在 1995 年提出了“优雅 K 串”的定义:这个字符串每一种字符的个数都是 $K$ 的倍数。

现在 ZZT 想要对字符串进行 $Q$ 次询问,第 $i$ 次询问给出一个区间 $[L_i, R_i]$,他想计算 $[L_i, R_i]$ 中有多少个子串是“优雅 K 串”。

由于 ZZT 忙于工作,所以他把这个问题交给了你,请你帮忙解决。

Input

第一行输入一个正整数 $K$。

第二行输入一个字符串 $S$。

第三行输入一个正整数 $Q$,表示有 $Q$ 次询问。

接下来 $Q$ 行,每行输入两个正整数 $L_i$ 和 $R_i$,表示第 $i$ 次询问。

Output

每次询问,输出一个正整数,表示满足条件的“优雅 K 串”的数量。

Constraints

$1 ≤ K ≤ 50$
$1≤ | S | ≤ 3 x 10^4$ 且 $S$ 仅包含小写英文字母
$1≤ Q ≤ 3 x 10^4$
$1 ≤ X_i≤ Y_i≤ N$

Sample 1 Input

1
abc
3
1 3
1 2
2 3

Sample 1 Output

6
3
3

HINT

牛客网

Source/Category

哈希