Бронирования и системы счисления

C++17airticket-sumdig

Авиакомпания «Технофлот» проводит розыгрыш призов по номерам бронирований!

Как известно, номер бронирования --- это строка из шести заглавных латинских букв или цифр. Номер бронирования считается выигрышным, если существует система счисления c основанием $b$, в которой справедливы следующие утверждения:

Все буквы и цифры являются корректными цифрами в данной системе счисления (считаем, что цифры идут в порядке от 0 к 9, затем от A (цифра 10) к Z (цифра 35); основание должно быть строго больше любой цифры числа).
Первая цифра числа не является нулём.
Сумма цифр числа $x+1$ в $b$-ичной системе счисления не должна быть равна сумме цифр числа $x$ плюс единица.

Вам дан шаблон --- некоторое число символов (от 0 до 6) заменено *. Если при некоторой замене звёздочек в шаблоне символами получается какой-то код бронирования, считается, что этот код соответствует шаблону. Ваша задача --- найти количество выигрышных бронирований, соответствующих данному шаблону.

Входные данные

Первая строка входных данных содержит одно целое число $t$ --- количество тестовых примеров ($1 \le t \le 10^4$). Каждая из последующих $t$ строк задаёт один тестовый пример и содержит по одной строке, имеющей длину 6 и состоящей из строчных латинских букв и цифр, а также знака *.

Выходные данные

Для каждого тестового примера выведите одно целое число --- количество выигрышных бронирований, соответствующих данному шаблону.

Примеры

Пример 1

Input

4
SAMPLE
123456
0ABCD*
9*BC*E

Output

Примечания

Задача состоит из пяти подзадач.

В первой подзадаче шаблоны не содержат звёздочек. Эта подзадача оценивается в 10 баллов.
Во второй подзадаче шаблоны содержат ровно одну звёздочку. Эта подзадача оценивается в 12 баллов.
В третьей подзадаче $t=1$. Эта подзадача оценивается в 16 баллов.
В четвёртой подзадаче первый и последний символ не являются звёздочками. Эта подзадача оценивается в 23 балла.
В пятой подзадаче дополнительных ограничений нет. Эта подзадача оценивается в 39 баллов.