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.