#P17845. [ONTAK 2021]SIL

[ONTAK 2021]SIL

阶乘缺失数字

把某个整数 nn 的阶乘 n!n! 写成无前导零的十进制字符串,然后将其中恰好 qq 个数字替换成 ?。请恢复这些数字。

输入格式

第一行测试用例数 TT。接下来 TT 行,每行一个只含数字和 ? 的字符串。每个字符串都由某个符合范围的阶乘替换若干位得到。保证补全方案存在且唯一。

输出格式

每个用例输出一行,包含恰好 qq 个数字:按输入字符串从左到右的顺序,输出各个 ? 对应的数字。不要输出完整阶乘。

数据范围

1≤T≤121\le T\le12,10≤n≤10000010\le n\le100000,1≤q≤91\le q\le9。输入不直接给出 nn。

样例

1
?4329??008?76640000
2021