CF1821A.Matching

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.

整数模板是一个由数字和/或问号组成的字符串。

一个正整数（严格大于 $0$）匹配该整数模板，当且仅当可以将模板中的每个问号替换为一个数字，使得所得字符串恰好是该整数的十进制表示，且不包含前导零。

例如：

• $42$ 匹配 4?；
• $1337$ 匹配 ????；
• $1337$ 匹配 1?3?；
• $1337$ 匹配 1337；
• $3$ 不匹配 ??；
• $8$ 不匹配 ???8；
• $1337$ 不匹配 1?7。

给定一个长度至多为 $5$ 的整数模板，请计算有多少个正整数（严格大于 $0$）匹配该模板。

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.

第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$）—— 测试用例的数量。

每个测试用例由一行组成，该行包含字符串 $s$（$1 \le |s| \le 5$），$s$ 由数字和/或问号组成——即对应测试用例的整数模板。

For each test case, print one integer — the number of positive (strictly greater than $0$) integers that match the template.

对于每个测试用例，输出一个整数——即满足该模板的正整数（严格大于 $0$）的个数。