你有一个字符串 s = s1s2... s|s|长度|s|,由小写英文字母组成。还有 q 个查询,每个查询由两个整数 li, ri (1 ≤ li ≤ ri ≤ |s|) 描述。查询的答案是字符串 s[li...ri] 的子串数量,这些子串是回文。
字符串 s[l... r] = slsl + 1... sr (1 ≤ l ≤ r ≤ |s|) 是字符串 s = s1s2... s|s| 的子字符串。
如果字符串 t 从左到右和从右到左读取相同,则称为回文。形式上,如果 t = t1t2... t|t| = t|t|t|t| - 1...t1。
输入
第一行包含字符串 s (1 ≤ |s| ≤ 5000)。第二行包含一个整数 q (1 ≤ q ≤ 106) — 查询数。接下来的 q 行包含查询。这些行中的第 i 行包含两个以空格分隔的整数 li, ri (1 ≤ li ≤ ri ≤ |s|) — 第 i 个查询的描述。
保证给定的字符串仅由小写英文字母组成。
输出
打印 q 个整数 — 查询的答案。按输入中给出的查询顺序打印答案。用空格分隔打印的数字。
示例
输入 #1
caaaba 5 1 1 1 4 2 3 4 6 4 5
输出 #1
1 7 3 4 2
注意
考虑第一个测试用例中的第四个查询。字符串 s[4...6] = «aba»。它的回文子串是:《a》、《b》、《a》、《aba》。