Автор: | Жюри зимних сборов 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 |
|
|