SP21640 NESPALIN - Nested Palindromes

回文数是指既可以正读也可以反读的整数。你朋友 Percy 最近对一种特别的回文数产生了兴趣，他将其称为「嵌套回文数」。这种数需要满足三个条件： 1. 数字本身是一个回文数。 2. 将数字从中间分开时，前半部分的数字也要是一个「嵌套回文数」。如果数字长度是奇数，则中间的数字不算在前半部分。 3. 任意两个相邻的数字不能相同。 Percy 声称他在纸上写下了一个没有前导零的「嵌套回文数」。然后，他将数中的一些数字擦掉并用问号替代，问你能否找出所有可能的完整数字，这些数字按照升序排列，并且可能符合 Percy 所写的数。当然，Percy 可能根本没有写出一个「嵌套回文数」。 Percy 还告诉你，他写的数在这个可能的列表中是第 **k** 个数。你的任务就是找到这个第 **k** 个数。

输入包含多组数据。首行输入一个整数 $T$，表示测试案例的数量。接下来有 $T$ 行，每行包含一个由数字和问号组成的字符串 $s$ 和一个整数 $k$。其中，$s$ 代表 Percy 擦掉数字后的结果，$k$ 表示你需要找出第 **k** 个数。

对每组数据，输出一行，给出符合条件的第 **k** 个数。如果不存在这样的数，则输出 `NONE`。

- $1 \le T \le 10$ - $1 \le |s| \le 20$ - $1 \le k \le 10^5$ - 字符串 $s$ 仅由数字和问号组成，且不包含前导零。 **本翻译由 AI 自动生成**