22062번 - Цифровые корни 다국어

Недавно Гриша придумал новую забаву: он выписывает по порядку все числа от a до b. Дима, заметив это, предложил выписывать не числа, а их цифровые корни, чтобы сэкономить место на доске. Грише очень понравилась эта идея, поэтому он решил как можно скорее узнать, что же такое цифровой корень числа.

Цифровой корень числа вычисляется следующим способом: берется сумма цифр данного числа, если она записывается одной цифрой, то она является цифровым корнем, иначе от этой суммы вычисляется сумма цифр до тех пор, пока не получится единственная цифра. Так цифровой корень 16 равен 7 (1+6=7), а цифровой корень 9991 равен 1 (9+9+9+1=28; 2+8=10; 1+0=1).

Пока Гриша начал выписывать цифровые корни на доску, Дима задался вопросом: какие цифры на доске будут написаны чаще всего.

Ваша задача состоит в том, чтобы по числам a и b, найти все цифровые корни, которые будут записаны на доске наибольшее количество раз.

Первая строка содержит целое положительное число t (1 ≤ t ≤ 10⁴) — число тестовых примеров во входных данных. Далее следуют описания тестовых примеров.

Каждый тестовый пример содержит в себе два натуральных числа a и b (1 ≤ a ≤ b ≤ 10¹⁵) — границы отрезка, который выписывает Гриша.

Выведите t строк. Для каждого тестового примера выведите число n — количество различных цифр, которые встретятся на доске наибольшее количество раз. Затем через пробел выведите n чисел в возрастающем порядке — цифры, которые встретятся на доске наибольшее количество раз.