Задача №114861. Тяжкий труд
Алексей работает математиком в известной компании «WordCount». Поскольку его проект недавно закрылся, в качестве замены ему выдали достаточно сомнительного вида задание: Алексей каждый месяц выписывает подряд числа в некотором интервале, а в конце месяца бухгалтерия производит подсчеты и выдает ему зарплату.
Зарплата Алексея вычисляется следующим образом: для начала в бухгалтерии находят такое \(x\), что среди выписанных Алексеем чисел есть число с \(x\) одинаковыми цифрами подряд, но нет числа с \(x+1\) одинаковой цифрой подряд. После чего количество чисел, в которых есть \(x\) одинаковых цифр подряд, и образует зарплату Алексея.
Алексей — умный математик и не хочет работать за гроши. Сегодня ему выдали план работы на следующие \(t\) месяцев. Помогите Алексею заранее посчитать, чему будет равна его зарплата в каждом месяце, если за \(i\)-й месяц он выпишет числа от \(l_i\) до \(r_i\) включительно, а в бухгалтерии ничего не перепутают.
В первой строке ввода дано единственное целое число \(t\) — количество месяцев, для которых надо посчитать зарплату Алексея (\(1 \leqslant t \leqslant 10^4\)).
В \(i\)-й из следующих \(t\) строк даны два целых числа \(l_i\) и \(r_i\) — концы отрезка чисел, которые Алексей выпишет в \(i\)-м месяце (\(1 \leqslant l_i \leqslant r_i \leqslant 10^{18}\)).
Для каждого месяца работы выведите на отдельной строке полученное число \(x\) и зарплату Алексея за этот месяц.
В первом примере между числами \(312\) и \(348\) находится число \(333\), в котором подряд идут три одинаковых цифры. Других чисел с тремя одинаковыми цифрами подряд между ними нет, поэтому ответ — « 3 1 ».
Во втором примере чисел с тремя одинаковыми цифрами подряд между \(223\) и \(329\) нет, а числа с двумя одинаковыми цифрами подряд делятся на числа вида
- \(\overline{22x}\) (от \(223\) до \(229\))
- \(\overline{2xx}\) (от \(233\) до \(299\))
- \(\overline{3xx}\) (\(300\), \(311\) и \(322\))
1 312 348
3 1
1 223 329
2 17