Рассмотрим последовательность цифр длины $$$2^k$$$ $$$[a_1, a_2, \ldots, a_{2^k}]$$$. Будем выполнять с ней следующую операцию: заменить пару $$$(a_{2i+1}, a_{2i+2})$$$ на $$$(a_{2i+1} + a_{2i+2})\bmod 10$$$ для $$$0\le i<2^{k-1}$$$. За каждое $$$i$$$ такое, что $$$a_{2i+1} + a_{2i+2}\ge 10$$$, мы получаем конфету! В результате, мы получим последовательность цифр длины $$$2^{k-1}$$$.

Менее формально, последовательность длины $$$2^k$$$ мы разбиваем на $$$2^{k-1}$$$ пар, каждая из которых состоит из двух чисел: первая пара состоит из первых двух чисел, вторая из третьего и четвертого, $$$\ldots$$$, последняя пара состоит из ($$$2^k-1$$$)-го и ($$$2^k$$$)-го чисел. За каждую пару, сумма чисел в которой не менее $$$10$$$, мы получаем конфету. После этого, мы заменяем каждую пару чисел на остаток от деления их суммы на $$$10$$$ (при этом сохраняем порядок чисел).

Будем выполнять данную операцию с последовательностью, пока она не станет длины $$$1$$$. Пусть $$$f([a_1, a_2, \ldots, a_{2^k}])$$$ обозначает количество конфет, которые мы получим в процессе.

К примеру: если изначальной последовательностью была $$$[8, 7, 3, 1, 7, 0, 9, 4]$$$, то:

После первой операции последовательность станет $$$[(8 + 7)\bmod 10, (3 + 1)\bmod 10, (7 + 0)\bmod 10, (9 + 4)\bmod 10]$$$ $$$=$$$ $$$[5, 4, 7, 3]$$$, и мы получим $$$2$$$ конфеты так как $$$8 + 7 \ge 10$$$ и $$$9 + 4 \ge 10$$$.

После второй операции последовательность станет $$$[(5 + 4)\bmod 10, (7 + 3)\bmod 10]$$$ $$$=$$$ $$$[9, 0]$$$, и мы получим еще одну конфету так как $$$7 + 3 \ge 10$$$.

После последней операции последовательность станет $$$[(9 + 0) \bmod 10]$$$ $$$=$$$ $$$[9]$$$.

Следовательно, $$$f([8, 7, 3, 1, 7, 0, 9, 4]) = 3$$$, так как мы получили всего $$$3$$$ конфеты.

Вам дана последовательность цифр длины $$$n$$$ $$$s_1, s_2, \ldots s_n$$$. Вы должны ответить на $$$q$$$ запросов вида $$$(l_i, r_i)$$$, где для $$$i$$$-го запроса вы должны вывести $$$f([s_{l_i}, s_{l_i+1}, \ldots, s_{r_i}])$$$. Гарантируется, что $$$r_i-l_i+1$$$ имеет вид $$$2^k$$$ для некоторого неотрицательного целого $$$k$$$.