Bạn được cung cấp hai chuỗi ~a~ và ~b~ có độ dài ~n~. Sau đó, bạn phải trả lời ~q~ truy vấn. Với mỗi truy vấn, bạn được cho một đoạn chỉ số từ ~l~ đến ~r~. Trong một phép biến đổi, bạn có thể chọn 1 chỉ số ~i~ (~1 \le i \le r~) và gán ~a_i = x~ với ~x~ là bất kỳ ký tự nào bạn muốn.

Yêu cầu: Hãy in ra số phép biến đổi tối thiểu bạn cần thực hiện để sorted(a[l..r]) = sorted(b[l..r]).

Lưu ý:

• Các phép biến đổi thực hiện trong một truy vấn không ảnh hưởng đến các truy vấn khác.
• Ở đây, với một chuỗi bất kỳ ~c~, sorted(c[l..r]) là chuỗi con từ ~l~ đến ~r~ của ~c~ đã được sắp xếp theo thứ tự từ điển.

INPUT

Dòng đầu chứa một số nguyên t (~1 \le t \le 1000~) — số lượng test.

Với mỗi test:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ (~1≤n,q≤2 \times 10^5~) — độ dài chuỗi và số lượng truy vấn.

• Dòng tiếp theo chứa chuỗi ~a~ có độ dài ~n~ gồm toàn chữ cái thường.

• Dòng tiếp theo chứa chuỗi ~b~ có độ dài ~n~ gồm toàn chữ cái thường.

• Sau đó là ~q~ dòng, mỗi dòng chứa hai số ~l~ và ~r~ (~1≤l≤r≤n~) — đoạn cần xét trong mỗi truy vấn.

• Đảm bảo rằng tổng của ~n + q~ của tất cả test không vượt quá ~2 \times 10^5~.

OUTPUT

Với mỗi truy vấn, in ra một số nguyên, là số phép biến đổi tối thiểu cần thực hiện, trên một dòng riêng biệt.

SAMPLE INPUT

2
5 3
abcde
edcba
1 5
1 4
3 3
4 2
zzde
azbe
1 3
1 4

SAMPLE OUTPUT

0
1
0
2
2

Giải thích:

• Truy vấn đầu tiên: sorted(a[1..5]) = abcde, sorted(b[1..5]) = abcde => không cần chỉnh sửa.
• Truy vấn thứ hai: cần đặt ~a_1 = e~, khi đó sorted(a[1..4]) = sorted(b[1..4]) = bcde

SUBTASKS