题目描述

整数模板是每位均为数字或问号的字符串。

如果可以用数字替换模板中的每个问号，从而获得该正整数（严格大于 $0$） 的十进制表示形式，且不带任何前导零，则该正整数与整数模板匹配。

例如：
$42$ 匹配 4?；
$1337$ 匹配 ????；
$1337$ 匹配 1?3?；
$1337$ 匹配 1337；
$3$ 不匹配 ??；
$8$ 不匹配 ???8；
$1337$ 不匹配 1?7；

你将获得一个最多包含 $5$ 个字符的整数模板。计算与其匹配的正整数（严格大于 $0$）的数量。

输入格式

本题包含多组数据
第一行包含一个正整数 $t$ 为数据组数。
每个测试用例由一行组成。其中包含每位均为数字或问号的字符串 $s$，即对应测试的整数模板。

输出格式

对于每个测试用例，输出一个整数：与模板匹配的正整数（严格大于 $0$）的数量。

说明/提示

$1 \le t \le 2 \times 10^{5}$， $t$ 为数据组数。
$1 \le |s| \le 5$，$|s|$ 为每组数据中字符串（整数模板）的长度。

翻译者：SCAR_L at 2023.04.30

样例

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

90
9
0
1
0
100
90
100