Finally, it's Tuesday, the day of the big contest (Div. 1). Bassam's rating is near 2100, so as a preparation, Bassam is going to buy his favorite drink, "3 in 1". He got everything set up and sat at his desk waiting for the contest to start. He solved the first problem, the second, the third—Bassam was on a roll! But suddenly, he spilled his drink all over the keyboard. Thankfully, the keyboard kept working, and Bassam continued his contest. After he finished, he went to chat with his friend Jamal, but to his surprise, the question mark key didn't work in English; when pressed, it printed the sentince "Ba3d Khamsa". So Bassam was stuck typing every question ending in "Ba3d Khamsa".

After all that, Jamal found a magical way to repair the keyboard. Now, Bassam always has a string $$$S$$$. Jamal considers a string $$$S$$$ magical if none of its substrings of length at least $$$2$$$ is a palindrome.

A palindrome is a string that reads the same backward as forward, for example strings 'z', 'aaa', 'aba', 'abccba' are palindromes, but strings 'codeforces', 'reality', 'ab' are not.

Bassam can perform this operation any number of times (possibly zero):

• Choose an index $$$i$$$ and change the character $$$S_i$$$ to any other English letter.

Now, you are given a string $$$S$$$ of size $$$N$$$ and $$$Q$$$ queries. For each query, you are given $$$L, R$$$ ($$$1 \le L \le R \le N$$$), and you should print the minimum number of operations required to make the substring $$$S[L:R]$$$ a magical string.

Note: The operations are hypothetical and do not change the original string $$$S$$$. You only need to compute the number of operations for each query.