Một chuỗi gọi chuỗi là đẹp nếu nó không chứa một chuỗi con đối xứng có độ dài ít nhất là 2.

Hãy định nghĩa chi phí của một chuỗi là số thao tác tối thiểu để chuỗi trở thành chuỗi đẹp. Mỗi thao tác, sẽ thay đổi bất kỳ ký tự nào của chuỗi thành một trong 3 chữ cái in thường đầu tiên của bảng chữ cái Latinh.

Bạn được cung cấp một chuỗi s có độ dài n, mỗi ký tự của chuỗi là một trong 3 chữ cái in thường đầu tiên của bảng chữ cái Latinh.

Bạn phải trả lời m truy vấn, mỗi truy vấn yêu cầu tính toán chi phí chuỗi con của chuỗi s từ vị trí l_i đến vị trí r_i.

input: nopalindrome.inp

• Dòng đầu tiên chứa hai số nguyên n và m (1 ≤ n, m ≤ 2*10⁵) - độ dài của chuỗi s và số lượng truy vấn.
• Dòng thứ hai chứa chuỗi s, bao gồm n ký tự, mỗi ký tự là một trong 3 chữ cái Latinh đầu tiên.
• m dòng sau chứa hai số nguyên l_i và r_i (1 ≤ l_i ≤ r_i ≤ n) - các tham số của truy vấn thứ i.

Output: nopalindrome.out

• Đối với mỗi truy vấn, in một số nguyên duy nhất - chi phí chuỗi con của chuỗi s từ vị trí l_i đến vị trí r_i.