Kolya, Vasya and the door

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Having painted to their heart’s content, Kolya and Vasya finally reached the door that they were actually supposed to paint. But after so many painted doors, just painting was no longer interesting to them. They decided to play a game. Since the builders had been dealing with paint all day, the rules of the game they came up with turned out to be quite strange.

At the beginning of the game, the builders choose some string \(s\) consisting solely of lowercase Latin letters. The game takes place in \(n\) rounds. Each round begins with Kolya choosing two numbers \(l_i\) and \(r_i\). Then Kolya writes on the door that part of the string \(s\) which starts with the character at index \(l_i\) and ends with the character at index \(r_i\) (1-based indexing). Vasya’s task is to paint over some of the letters written by Kolya so that the resulting string reads the same from left to right and from right to left.

Nobody understood which of the builders won and why they had so much fun, but what’s the difference? They were happy and that’s what matters.

Your task is to find the minimum number of characters Vasya could have painted over in each round of the game so that the string reads the same from both sides.

Input

The first line gives the string \(s\) — a sequence of lowercase Latin characters.

The second line contains a single positive integer \(n\) — the number of rounds of the game.

The third line contains \(n\) pairs of numbers \(l_i\) and \(r_i\) — the left and right boundaries for each round.

Output

In a single line, print \(n\) positive integers — the answers for each round.

Constraints

\(30 \%\) of tests: \(1 \le |s|, n \le 100\),

\(70 \%\) of tests: \(1 \le |s| \le 10^3, 1 \le n \le 10^5\).

Samples

Input (stdin) сopy	Output (stdout) сopy
cabcbaab 3 1 5 2 6 6 8	2 0 1

Notes

The string for the first round is \(\texttt{cabcb}\). You need to delete both \(\texttt{b}\) characters, or the first two characters. The string for the second round \(\texttt{abcba}\) reads the same from both sides. For the string of the third round \(\texttt{aab}\), you need to delete the \(\texttt{b}\) character.