После долгих лет поисков, Иван наконец-то нашёл на свалке свою флешку с паролем от криптокошелька. К сожалению данные оказались повреждены, и пароль удалось восстановить не полностью.

Символы, которые не поддались восстановлению, обозначены как «?».

К счастью, Иван помнит, что для пароля выполнялись следующие условия:

в пароле использовались только десятичные цифры, то есть символы 0-9. если прочитать пароль как десятичное число, то оно будет не менее L и не более R. Чтобы оценить печальность ситуации, Иван интересуется, сколько паролей подходит под условия выше.

Входные данные Первая строка входного файла INPUT.TXT содержит целое число T – количество наборов входных данных (1 ≤ T ≤ 1000).

Каждый набор состоит из двух строк: в первой содержится n символов из повреждённого пароля (1 ≤ n ≤ 15), а во второй два целых числа L и R, записанных через пробел (0 ≤ L ≤ R ≤ 10^15).

Выходные данные В выходной файл OUTPUT.TXT на каждый тестовый набор выведите ответ в отдельной строке – количество подходящих паролей.

Ввод: 4 ??? 10 100 2?0 123 456 20?? 2023 2023 ?? 100 999 Вывод: 91 10 1 0