题号：NC17064
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld
题目描述
ZZT 得到了一个字符串 S 以及一个整数 K。
WZH 在 1995 年提出了“优雅 K 串”的定义：这个字符串每一种字符的个数都是 K 的倍数。
现在 ZZT 想要对字符串进行 Q 次询问，第 i 次询问给出一个区间 [Li, Ri]，他想计算 [Li, Ri] 中有多少个子串是“优雅 K 串”。
由于 ZZT 忙于工作，所以他把这个问题交给了你，请你帮忙解决。
输入描述:
第一行输入一个正整数 K。
第二行输入一个字符串 S。
第三行输入一个正整数 Q，表示有 Q 次询问。
接下来 Q 行，每行输入两个正整数 Li 和 Ri，表示第 i 次询问。
1 ≤ K ≤ 50.
1≤ | S | ≤ 3 x 104 且 S 仅包含小写英文字母.
1≤ Q ≤ 3 x 104.
1 ≤ Xi ≤ Yi ≤ N.
输出描述:
每次询问，输出一个正整数，表示满足条件的“优雅 K 串”的数量。