[Solution] Building Palindromes Kick Start Solution

[Solution] Building Palindromes Kick Start Solution

Anna has a row of N$N$ blocks, each with exactly one letter from A to Z written on it. The blocks are numbered 1,2,⋯,N$1,2,\cdots ,\mathbf{N}$ from left to right.

Today, she is learning about palindromes. A palindrome is a string that is the same written forwards and backwards. For example, ANNA, RACECAR, AAA and X are all palindromes, while AB, FROG and YOYO are not.

Bob wants to test how well Anna understands palindromes, and will ask her Q$Q$ questions. The i-th question is: can Anna form a palindrome using all of the blocks numbered from Li$L_i$ to Ri$R_i$, inclusive? She may rearrange the blocks if necessary. After each question, Anna puts the blocks back in their original positions.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Please help Anna by finding out how many of Bob's questions she can answer "yes" to.

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow. Each test case starts with a line containing the two integers N$N$ and Q$Q$, the number of blocks and the number of questions,

Sherlock and Parentheses Kick Start Solution

Building Palindromes Kick Start Solution

Irregular Expressions Kick Start Solution

Parcels Kick Start Solution

 respectively. Then, another line follows, containing a string of N$N$ uppercase characters (A to Z). Then, Q$Q$ lines follow. The i-th line contains the two integers Li$L_i$ and Ri$R_i$, describing the i-th question.

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1$1$) and y$y$ is the number of questions Anna can answer "yes" to.

Limits

Time limit: 30 seconds.
Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
1≤Li≤Ri≤N$1\le L_i\le R_i\le \mathbf{N}$.

Test Set 1

1≤N≤20$1\le \mathbf{N}\le 20$.
1≤Q≤20$1\le \mathbf{Q}\le 20$.

Test Set 2

1≤N≤100000$1\le \mathbf{N}\le 100000$.
1≤Q≤100000$1\le \mathbf{Q}\le 100000$.