Ilya the Lion wants to help all his friends with passing exams. They need to solve the following problem to pass the IT exam.

You've got string *s* = *s*<sub class="lower-index">1</sub>*s*<sub class="lower-index">2</sub>... *s*<sub class="lower-index">*n*</sub> (*n* is the length of the string), consisting only of characters "." and "#" and *m* queries. Each query is described by a pair of integers *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> &lt; *r*<sub class="lower-index">*i*</sub> ≤ *n*). The answer to the query *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> is the number of such integers *i* (*l*<sub class="lower-index">*i*</sub> ≤ *i* &lt; *r*<sub class="lower-index">*i*</sub>), that *s*<sub class="lower-index">*i*</sub> = *s*<sub class="lower-index">*i* + 1</sub>.

Ilya the Lion wants to help his friends but is there anyone to help him? Help Ilya, solve the problem.
The first line contains string *s* of length *n* (2 ≤ *n* ≤ 10<sup class="upper-index">5</sup>). It is guaranteed that the given string only consists of characters "." and "#".

The next line contains integer *m* (1 ≤ *m* ≤ 10<sup class="upper-index">5</sup>) — the number of queries. Each of the next *m* lines contains the description of the corresponding query. The *i*-th line contains integers *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> &lt; *r*<sub class="lower-index">*i*</sub> ≤ *n*).
#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::string inp;
    std::cin >> inp;

    std::unordered_map<std::string, int> storage;

    int test_cases;
    std::cin >> test_cases;

    for (int _ = 0; _ < test_cases; ++_) {
        int inp1, inp2;
        std::cin >> inp1 >> inp2;
        std::string temp = inp.substr(inp1 - 1, inp2 - inp1 + 1);
        int res = 0;

        if (storage.find(temp) == storage.end()) {
            for (int a = inp1 - 1; a < inp2 - 1; ++a) {
                if (inp[a] == inp[a + 1]) {
                    res += 1;
                }
            }
            storage[temp] = res;
        } else {
            res = storage[temp];
        }

        std::cout << res << std::endl;
    }

    return 0;
}
