Tewi đã ốm liệt giường nên Yagokoro Eirin phải chữa bệnh cho cô. Đoạn ADN của Tewi có độ dài ~n~ gồm cách kí tự ~a, b, c~ (vì sao thì chưa rõ). Eirin có thể sửa đổi một vị trí bất kì trên ADN với chi phí là 1.

Cô đang nghi ngờ ~q~ đoạn con ~[l_i, r_i]~ có thể là nguyên nhân gây bệnh. Với mỗi đoạn ADN con này, Eirin muốn sửa lại đoạn này sao cho không tồn tại đoạn con nào có độ dài lớn hơn 1 là xâu đối xứng. Ví dụ ~aab~ là không thỏa mãn vì có ~aa~ là xâu đối xứng. Hãy giúp cô tính trước chi phí để chữa bệnh nhé!

Input:

• Dòng đầu tiên gồm 2 số ~n, q~.
• Dòng tiếp theo là một xâu gồm ~n~ kí tự chỉ gồm ~a, b, c~.
• ~q~ dòng tiếp theo mỗi dòng gồm 2 số ~l_i, r_i~.

Output:

• ~q~ dòng là chi phí chữa bệnh.

Sample Test

Input:

5 4
baacb
1 3
1 5
4 5
2 3

Output:

1
2
0
1

Giới hạn:

• Trong mọi test ~n, q \le 10^5~
• 10% số điểm: ~n, q \le 5~.
• 30% số điểm: ~n, q \le 2000~.
• 30% số điểm: ADN chỉ gồm 2 kí tự ~a, b~.
• 30% số điểm: Không có giới hạn gì thêm.