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

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

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

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

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

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

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

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

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

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