Задача 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. Определим Srl как подстроку S, состоящую из всех её элементов с номерами от l до r, включительно. Например, S61 = 112121, S1717 = 2.

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

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

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

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

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

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

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

0.080s 0.017s 13