A. Сопоставление
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Целочисленный шаблон — это строка, состоящая из цифр и/или знаков вопроса.

Положительное (строго больше $$$0$$$) целое число сопоставляется с шаблоном, если можно заменить каждый знак вопроса в шаблоне на цифру так, что мы получим десятичную запись этого числа без лишних нулей.

Например:

  • $$$42$$$ сопоставляется с 4?;
  • $$$1337$$$ сопоставляется с ????;
  • $$$1337$$$ сопоставляется с 1?3?;
  • $$$1337$$$ сопоставляется с 1337;
  • $$$3$$$ не сопоставляется с ??;
  • $$$8$$$ не сопоставляется с ???8;
  • $$$1337$$$ не сопоставляется с 1?7.

Вам дан целочисленный шаблон, состоящий из не более $$$5$$$ символов. Посчитайте количество положительных (строго больших $$$0$$$) целых чисел, которые сопоставляются с ним.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из одной строки $$$s$$$ ($$$1 \le |s| \le 5$$$), состоящей из цифр и/или знаков вопроса. Эта строка является целочисленным шаблоном для соответствующего набора входных данных.

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

Для каждого набора входных данных выведите одно целое число — количество положительных (строго больших $$$0$$$) целых чисел, которые сопоставляются с заданным шаблоном.

Пример
Входные данные
8
??
?
0
9
03
1??7
?5?
9??99
Выходные данные
90
9
0
1
0
100
90
100