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

Условие

Построим бесконечную последовательность строк S₀, S₁, S₂, … из двух символов — цифр 1 и 2 — следующим образом: S₀ = 1; S_i + 1 получается из S_i одновременной заменой всех цифр 1 на строки 11212, а всех цифр 2 — на 1121212.

Так, S₁ = 11212, S₂ = 11212112121121212112121121212, ….

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

Определим S_∞ как бесконечную последовательность цифр, содержащую в качестве префиксов все строки S_i. Определим Srl как подстроку S_∞, состоящую из всех её элементов с номерами от l до r, включительно. Например, S61 = 112121, S1717 = 2.

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

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

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

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

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

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

2
1 6
17 17

8
2