Автор: | Жюри зимних сборов 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 (1≤t≤50000) — количество запросов. В следующих t строках записаны запросы; i-я из них содержит два целых числа li и ri, разделённых одним пробелом (1≤li≤ri≤109).
Выведите в выходной файл t чисел, по одному числу на строке — ответы на запросы в том порядке, в котором они заданы во входном файле.
№ | Входной файл (digitsum.in ) |
Выходной файл (digitsum.out ) |
---|---|---|
1 |
|
|