题目描述

定义一个 “模板串“ 为一个由数字字符和 "?" 组成的字符串。我们可以通过将问号替换成数字字符来得到正整数。显然，一个模板串可能会和多个正整数匹配。

例如: "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。