该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定一个长度为 $n$ 的字符串$s$（仅含小写字母），以及 $q$ 次独立的区间查询。每次查询给出一对整数 $(l, r)$，表示子串
$s_l\,s_{l+1}\,\dots\,s_r.$

你需要输出让该区间变得可回文的 最少字符修改数量。

我们称一个区间是可回文的当且仅当至少存在一种对该区间内的字符进行重新排列的方法，使该区间重新排列之后是回文串。

每次修改是独立的，即仅针对本次查询，与之后的询问无关。

Format

Input

第一行包含两个整数 $1 \le n, q \le 5*10^3$——字符串长度和查询次数。
第二行是长度为 $n$ 的字符串 $s$，仅由 'a'–'z' 组成。
接下来 $q$ 行，每行给出一对整数 $(l_i, r_i)$（$1 \le l_i \le r_i \le n$）。

Output

对每个查询 $(l_i,r_i)$，输出最少字符修改数量。

Samples

10 5
abacabaaxy
1 7
4 6
1 10
8 10
2 9

0
1
2
1
1

对区间(4,6)来说，可以选择将a替换为c,变成ccb，然后重新排序为cbc构成回文串，仅需修改一次即可。