{"raw_statement":[{"iden":"problem statement","content":"For a string $X = X_1X_2\\dots X_{|X|}$ and positive integers $l,r~(1 \\leq l \\leq r \\leq |X|)$, let $X_{l,r} = X_l X_{l+1}\\dots X_r$.\nYou are given a string $S=S_1S_2\\dots S_{|S|}$ consisting of `A` and `B`.  \nYou are given $Q$ queries. For each query, answer the following question:\n\n*   Starting from the state $T = S_{l,r}$, find the minimum possible length of a palindrome that can be obtained by performing the operation \"choose one occurrence of `AB` that appears as a contiguous substring in $T$ and delete it\" zero or more times.  \n    If no palindrome can be obtained regardless of how the operation is performed, output `-1`."},{"iden":"constraints","content":"*   $1 \\leq |S| \\leq 4 \\times 10^5$\n*   $1 \\leq Q \\leq 5 \\times 10^4$\n*   $1 \\leq l \\leq r \\leq |S|$\n*   $S$ is a string consisting of `A` and `B`.\n*   $Q,l,r$ are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$S$\n$Q$\n$\\mathrm{Query}_1$\n$\\mathrm{Query}_2$\n$\\vdots$\n$\\mathrm{Query}_Q$\n\n$\\mathrm{Query}_q$ represents the $q$\\-th query and is given in the following format:\n\n$l$ $r$"},{"iden":"sample input 1","content":"ABBABB\n5\n1 6\n4 5\n3 5\n2 3\n3 4"},{"iden":"sample output 1","content":"2\n0\n1\n2\n-1\n\nFor the first, second, and third queries, by performing the operation as follows, you can obtain a palindrome with the minimum length among those obtained by the operation.\n\n*   `ABBABB` $\\rightarrow$ `ABBB` $\\rightarrow$ `BB`\n*   `AB` $\\rightarrow$ (empty string)\n*   `BAB` $\\rightarrow$ `B`"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}