Loading [MathJax]/jax/output/CommonHTML/jax.js

Задача K. (20081226) Сумма цифр в строке

Автор:Жюри зимних сборов 2009   Ограничение времени:2 сек
Входной файл:digitsum.in   Ограничение памяти:64 Мб
Выходной файл:digitsum.out  
Максимальный балл:100  

Условие

Построим бесконечную последовательность строк S0, S1, S2, из двух символов — цифр 1 и 2 — следующим образом: S0=1; Si+1 получается из Si одновременной заменой всех цифр 1 на строки 11212, а всех цифр 2 — на 1121212.

Так, S1=11212, S2=11212112121121212112121121212, .

Заметим, что каждая строка содержит в качестве префиксов все предыдущие.

Определим S как бесконечную последовательность цифр, содержащую в качестве префиксов все строки Si. Определим §rl как подстроку S, состоящую из всех её элементов с номерами от l до r, включительно. Например, §61=112121, S1717=2.

По данным числам l и r найдите сумму цифр в строке Srl.

Формат входного файла

Первая строка входного файла содержит целое число t (1t50000) — количество запросов. В следующих t строках записаны запросы; i-я из них содержит два целых числа li и ri, разделённых одним пробелом (1liri109).

Формат выходного файла

Выведите в выходной файл t чисел, по одному числу на строке — ответы на запросы в том порядке, в котором они заданы во входном файле.

Примеры тестов

Входной файл (digitsum.in) Выходной файл (digitsum.out)
1
2
1 6
17 17
8
2

0.056s 0.011s 13