팰린드롬 만들기

Anna에게 N개의 블록이 한 줄로 놓여 있으며, 각 블록에는 A부터 Z까지의 문자 중 정확히 하나가 적혀 있다. 블록에는 왼쪽에서 오른쪽으로 1, 2, ..., N의 번호가 매겨져 있다.

오늘 Anna는 팰린드롬에 대해 배우고 있다. 팰린드롬은 앞에서부터 쓴 문자열과 뒤에서부터 쓴 문자열이 같은 문자열이다. 예를 들어, ANNA, RACECAR, AAA, X는 모두 팰린드롬이지만, AB, FROG, YOYO는 그렇지 않다.

Bob은 Anna가 팰린드롬을 얼마나 잘 이해하는지 시험하기 위해 Anna에게 Q개의 질문을 한다. i번째 질문은 다음과 같다. Anna가 $L_{i}$부터 $R_{i}$까지의 번호가 매겨진 블록을 모두 사용하여, 필요하다면 블록을 재배열해 팰린드롬을 만들 수 있는가? 각 질문이 끝난 뒤 Anna는 블록을 원래 위치에 돌려놓는다.

Bob의 질문 중 Anna가 "yes"라고 답할 수 있는 질문이 몇 개인지 알아내어 Anna를 도와주자.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ $L_{i}$ ≤ $R_{i}$ ≤ N.

테스트 세트 1 (공개)

1 ≤ N ≤ 20. 1 ≤ Q ≤ 20.

테스트 세트 2 (비공개)

1 ≤ N ≤ $10^{5}$. 1 ≤ Q ≤ $10^{5}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 블록의 수와 질문의 수를 각각 나타내는 두 정수 N과 Q가 포함된 한 줄로 시작한다. 그다음 줄에는 N개의 대문자 문자를 포함하는 문자열이 주어진다(문자는 A부터 Z까지이다). 그다음 Q개의 줄이 주어진다. i번째 줄에는 i번째 질문을 나타내는 두 정수 $L_{i}$부터 $R_{i}$까지가 포함된다.

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

예제 케이스 #1에서 N = 7이고 Q = 5이다.

• 첫 번째 질문에서 Anna는 블록 AACC을 사용해야 한다. Anna는 이 블록들을 팰린드롬 ACCA(또는 CAAC)으로 재배열할 수 있다.

• 두 번째 질문에서 Anna는 블록 A을 사용해야 한다. 이는 이미 팰린드롬이므로 재배열할 필요가 없다.

• 세 번째 질문에서 Anna는 블록 BAAC을 사용해야 한다. 이 블록들은 팰린드롬으로 재배열할 수 없다.

• 네 번째 질문에서 Anna는 블록 CA을 사용해야 한다. 이 블록들은 팰린드롬으로 재배열할 수 없다.

• 다섯 번째 질문에서 Anna는 블록 AACCA을 사용해야 한다. Anna는 이 블록들을 재배열하여 팰린드롬 ACACA(또는 CAAAC)을 만들 수 있다.

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

예제 케이스 #2에서 N = 3이고 Q = 5이다. 첫 번째 질문에서 Anna는 블록 XYZ을 사용하여 팰린드롬을 만들어야 한다. 이는 불가능하며, Bob의 나머지 질문도 첫 번째 질문과 같으므로 정답은 0이다.