회문 만들기

Anna는 N개의 블록을 한 줄로 가지고 있고, 각 블록에는 A부터 Z까지의 알파벳 대문자 하나가 적혀 있다. 블록은 왼쪽에서 오른쪽으로 1, 2, ..., N번이 매겨져 있다.

오늘 Anna는 회문을 배우고 있다. 회문은 앞에서 읽으나 뒤에서 읽으나 같은 문자열이다. 예를 들어 ANNA, RACECAR, AAA, X는 모두 회문이고, AB, FROG, YOYO는 회문이 아니다.

Bob은 Anna가 회문을 얼마나 잘 이해하는지 시험하려고 Q개의 질문을 한다. i번째 질문은 다음과 같다. Anna가 Li번부터 Ri번까지의 블록을 전부 사용해서, 필요하면 순서를 바꾸어 회문을 만들 수 있는가? 질문이 끝날 때마다 Anna는 블록을 원래 위치에 되돌려 놓는다.

Bob의 질문 중 Anna가 "yes"라고 답할 수 있는 개수를 구하자.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 블록의 수 N과 질문의 수 Q가 주어진다. 그다음 줄에는 N개의 알파벳 대문자(A부터 Z까지)로 이루어진 문자열이 주어진다. 그다음 Q개의 줄이 이어지며, i번째 줄에는 i번째 질문을 나타내는 두 정수 Li, Ri가 주어진다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 Anna가 "yes"라고 답할 수 있는 질문의 수이다.

• 1 ≤ T ≤ 100.
• 1 ≤ Li ≤ Ri ≤ N.

Sample Case #1에서 N = 7, Q = 5이다.

• 첫 번째 질문에서 Anna는 블록 AACC를 사용해야 한다. 이 블록들은 회문 ACCA(또는 CAAC)로 재배열할 수 있다.
• 두 번째 질문에서 Anna는 블록 A를 사용해야 한다. 이것은 이미 회문이므로 재배열할 필요가 없다.
• 세 번째 질문에서 Anna는 블록 BAAC를 사용해야 한다. 이 블록들은 회문으로 재배열할 수 없다.
• 네 번째 질문에서 Anna는 블록 CA를 사용해야 한다. 이 블록들은 회문으로 재배열할 수 없다.
• 다섯 번째 질문에서 Anna는 블록 AACCA를 사용해야 한다. 이 블록들은 회문 ACACA(또는 CAAAC)로 재배열할 수 있다.

Anna는 Bob의 질문 중 3개에 "yes"라고 답할 수 있으므로 답은 3이다.

Sample Case #2에서 N = 3, Q = 5이다. 첫 번째 질문에서 Anna는 블록 XYZ를 사용해 회문을 만들어야 한다. 이것은 불가능하고, 나머지 질문도 첫 번째 질문과 같으므로 답은 0이다.