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 
. Além disso, ele faz 
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 
a 
do texto.
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.
Entrada
A primeira linha contém a string 
A segunda linha contém um único inteiro 
- o número de perguntas. As próximas linhas contêm as perguntas. A i-ésima dessas linhas contém dois inteiros e 
a descrição da i-ésima pergunta.
Saída
Imprima 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 |