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

Problem

You are given two strings $a$ and $b$ of length $n.$ Then, you are (forced against your will) to answer $q$ queries.

For each query, you are given a range bounded by $l$ and $r$. In one operation, you can choose an integer $i(l≤i≤r)$ and set $a_i=x$ where $x$ is any character you desire. Output the minimum number of operations you must perform such that sorted$(a[l..r])$=sorted$(b[l..r])$. The operations you perform on one query does not affect other queries.

For an arbitrary string $c$, sorted$(c[l..r])$denotes the substring consisting of characters $c_l,c_{l+1},...,c_r$ sorted in lexicographical order.

Input

The first line contains $t(1≤t≤1000)$ – the number of test cases.

The first line of each test case contains two integers $n$ and $q (1≤n,q≤2⋅10^5)$ – the length of both strings and the number of queries.

The following line contains a of length $n$. It is guaranteed a only contains lowercase latin letters.

The following line contains $b$ of length $n.$ It is guaranteed b only contains lowercase latin letters.The following $q$ lines contain two integers $l$ and $r(1≤l≤r≤n)$ – the range of the query.

It is guaranteed the sum of $n$ and $q$ over all test cases does not exceed $2⋅10^5$ .

Output

For each query, output an integer, the minimum number of operations you need to perform in a new line.

Example : in

3
5 3
abcde
edcba
1 5
1 4
3 3
4 2
zzde
azbe
1 3
1 4
6 3
uwuwuw
wuwuwu
2 4
1 3
1 6

Example : out

0
1
0
2
2
1
1
0

Note

For the first query, sorted$(a[1..5])= abcde$ and sorted$(b[1..5])= abcde$, so no operations are necessary.

For the second query, you need to set $a_1=e.$ Then, sorted$(a[1..4])$ $=$ sorted$(b[1..4]) = bcde$.