120. 小红的数字匹配
内存限制：256 MB
时间限制：1.000 S
题目描述
定义一个 “模板串“ 为一个由数字字符和 "?" 组成的字符串。我们可以通过将问号替换成数字字符来得到正整数。显然，一个模板串可能会和多个正整数匹配。
例如: "1?2"可以和 102 或者 132 等正整数匹配。请注意，匹配的正整数不能包含前导零，例如"??1"可以匹配101，但不能匹配 001。小红拿到了一个模板串，她想知道，和这个模板串匹配的正整数中，第 k 小的是多少?
输入
第一行输入一个正整数 t，代表询问次数。接下来的 2 * t 行，每两行为一次询问: 第一行输入一个字符串，仅由数字字符和 '?' 组成。第二行输入一个正整数 k，代表询问的是第 k 小。
输出
输出 t 行，每行输出一个答案。如果一共都没有k个匹配的正整数，则输出 -1。否则输出第小的匹配的正整数。
样例输入 复制
4
??1
1
22?
100000000
2??
3
000???
1
样例输出 复制
101
-1
202
-1提示
数据范围：
1 ≤ t ≤ 10^4 1 ≤ k ≤ 10^9
字符串长度不超过 30。