Matching
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
An integer template is a string consisting of digits and/or question marks.
A positive (strictly greater than $0$) integer matches the integer template if it is possible to replace every question mark in the template with a digit in such a way that we get the decimal representation of that integer without any leading zeroes.
For example:
- $42$ matches 4?;
- $1337$ matches ????;
- $1337$ matches 1?3?;
- $1337$ matches 1337;
- $3$ does not match ??;
- $8$ does not match ???8;
- $1337$ does not match 1?7.
You are given an integer template consisting of at most $5$ characters. Calculate the number of positive (strictly greater than $0$) integers that match it.
The first line contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases.
Each test case consists of one line containing the string $s$ ($1 \le |s| \le 5$) consisting of digits and/or question marks — the integer template for the corresponding test case.
For each test case, print one integer — the number of positive (strictly greater than $0$) integers that match the template.
Input
The first line contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases.
Each test case consists of one line containing the string $s$ ($1 \le |s| \le 5$) consisting of digits and/or question marks — the integer template for the corresponding test case.
Output
For each test case, print one integer — the number of positive (strictly greater than $0$) integers that match the template.
8
??
?
0
9
03
1??7
?5?
9??99
90
9
0
1
0
100
90
100