André, o Linguista
André, um jovem estudante de linguística, está analisando uma obra escrita em uma linguagem desconhecida. Ele suspeita que o texto está escrito em Linguaugnil, uma antiga língua falada no continente europeu. Tal idioma possui uma marcante característica: todas as palavras de seu léxico, quando escritas no alfabeto latino, formam palíndromos, assim como todo palíndromo forma uma palavra válida.
Em busca de confirmar sua hipótese, o estudante lhe fornece o texto, representado por uma string $$S$$. Além disso, ele faz $$Q$$ perguntas, as quais você deve responder com o número de palavras válidas (na língua Linguaugnil) formadas por um sub-intervalo do trecho de $$L_i$$ a $$R_i (1 \le i \le Q)$$ do texto.
[spoiler title=’Palíndromo – Definição’ style=’default’ collapse_link=’true’]Uma palavra é chamada de palíndromo se, e somente se, tiver a mesma leitura da esquerda para a direita e da direita para a esquerda. A palavra “arara”, por exemplo, forma um palíndromo, enquanto “acaba” não constitui um palíndromo.[/spoiler]
Entrada
A primeira linha contém a string $$S (1 \le |S| \le 5 \times 10^3)$$ A segunda linha contém um único inteiro $$Q (1 \le Q \le 10^6)$$ – o número de perguntas. As próximas $$Q$$ linhas contêm as perguntas. A i-ésima dessas linhas contém dois inteiros $$L_i$$ e $$R_i (1 \le L_i \le R_i \le |S|)$$ a descrição da i-ésima pergunta.
Saída
Imprima $$Q$$ inteiros – as respostas às perguntas. Imprima as respostas na ordem em que as consultas são fornecidas na entrada, separando os números impressos por espaços.
| Entrada | Saída |
caaaba 5 1 1 1 4 2 3 4 6 4 5 |
1 7 3 4 2 |