## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Building Palindromes KickStart Solution | Kick Start 2022

Anna has a row of $N$ blocks, each with exactly one letter from A to Z written on it. The blocks are numbered $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, ANNARACECARAAA and X are all palindromes, while ABFROG and YOYO are not.

Bob wants to test how well Anna understands palindromes, and will ask her $Q$ questions. The i-th question is: can Anna form a palindrome using all of the blocks numbered from ${L}_{i}$ to ${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:-  👉
👇👇👇👇👇

### Input

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

respectively. Then, another line follows, containing a string of $N$ uppercase characters (A to Z). Then, $Q$ lines follow. The i-th line contains the two integers ${L}_{i}$ and ${R}_{i}$, describing the i-th question.

### Output

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

### Limits

Time limit: 30 seconds.
Memory limit: 1 GB.
$1\le \mathbf{T}\le 100$.
$1\le {L}_{i}\le {R}_{i}\le \mathbf{N}$.

#### Test Set 1

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

#### Test Set 2

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