310355: CF1821A. Matching

A. Matchingtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

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.

ExampleInput

8
??
?
0
9
03
1??7
?5?
9??99

Output

90
9
0
1
0
100
90
100

题目大意：
题目名为 "匹配"。在这个问题中，一个整数模板是一个由数字和/或问号组成的字符串。一个大于0的整数如果能够通过将模板中的每个问号替换为一个数字，使得替换后的字符串是该整数的十进制表示（且没有前导零），则认为该整数与整数模板匹配。

输入输出数据格式：
输入：
- 第一行包含一个整数 t (1 ≤ t ≤ 2 × 10^4)，表示测试用例的数量。
- 每个测试用例包含一行，该行是一个由数字和/或问号组成的字符串 s (1 ≤ |s| ≤ 5)，表示对应的测试用例的整数模板。

输出：
- 对于每个测试用例，输出一个整数，表示有多少个大于0的整数与该模板匹配。

例如：
输入：
```
8
??
?
0
9
03
1??7
?5?
9??99
```
输出：
```
90
9
0
1
0
100
90
100
```

请注意，由于您请求的是题目大意以及输入输出数据格式，所以没有提供具体的 LaTeX 格式的公式。如果需要具体的 LaTeX 格式公式，请指出具体哪个部分需要转换。题目大意： 题目名为 "匹配"。在这个问题中，一个整数模板是一个由数字和/或问号组成的字符串。一个大于0的整数如果能够通过将模板中的每个问号替换为一个数字，使得替换后的字符串是该整数的十进制表示（且没有前导零），则认为该整数与整数模板匹配。 输入输出数据格式： 输入： - 第一行包含一个整数 t (1 ≤ t ≤ 2 × 10^4)，表示测试用例的数量。 - 每个测试用例包含一行，该行是一个由数字和/或问号组成的字符串 s (1 ≤ |s| ≤ 5)，表示对应的测试用例的整数模板。 输出： - 对于每个测试用例，输出一个整数，表示有多少个大于0的整数与该模板匹配。 例如： 输入： ``` 8 ?? ? 0 9 03 1??7 ?5? 9??99 ``` 输出： ``` 90 9 0 1 0 100 90 100 ``` 请注意，由于您请求的是题目大意以及输入输出数据格式，所以没有提供具体的 LaTeX 格式的公式。如果需要具体的 LaTeX 格式公式，请指出具体哪个部分需要转换。