狮子伊利亚想要帮助他所有的朋友通过考试。他们需要解决以下问题才能通过 IT 考试。
你有字符串 s = s1s2... sn (n 是字符串的长度),仅由字符“.”组成。和“#”和 m 查询。每个查询由一对整数 li, ri (1 ≤ li < ri ≤ n) 描述。查询 li, ri 的答案是此类整数 i (li ≤ i < ri) 的数量,即 si = si + 1。
狮子伊利亚想要帮助他的朋友,但是有人可以帮助他吗?帮助伊利亚,解决问题。
输入
第一行包含长度为 n (2 ≤ n ≤ 105) 的字符串 s。保证给定的字符串仅由字符“.”组成。和 ”#”。
下一行包含整数 m (1 ≤ m ≤ 105) — 查询数。接下来的 m 行中的每一行都包含相应查询的描述。第 i 行包含整数 li, ri (1 ≤ li < ri ≤ n)。
输出
打印 m 个整数 — 按照输入中给出的顺序查询的答案。
示例
输入 #1
...... 4 3 4 2 3 1 6 2 6
输出 #1
1 1 5 4
输入 #2
#..### 5 1 3 5 6 1 5 3 6 3 4
输出 #2
1 1 2 2 0