P1643 Perfect Number

During an expedition, the archaeologist Xiaoxing accidentally fell into an abyss and traveled to a mysterious desert. Many things here are beyond his understanding, such as buildings floating in the air and all kinds of strange animals. In the center of the desert, Xiaoxing found a huge temple-like structure. To escape this place, he decided to explore it. As he approached the temple gate, a human-faced lion suddenly leaped out (not the Sphinx)! It roared: "I am the guardian here. To pass, you must answer my series of questions; otherwise, I will eat you." The human-faced lion told Xiaoxing that the questions always follow this pattern: What is the $N$-th smallest palindrome greater than $X$? Xiaoxing thought the problem did not seem difficult, so the Q&A began. "What is the 1st smallest palindrome greater than $1$?" "$2$." "What is the 2nd smallest palindrome greater than $17$?" "$33$." "What is the 2nd smallest palindrome greater than $98$?" "$101$." "Then what is the 2,339,587-th smallest palindrome greater than $948237$?" "*(•%(∗•—#•#￥∗—%(∗—%" To avoid being eaten by the guardian, Xiaoxing opened his laptop to seek help, and he unexpectedly found you through the network (Netcom? Telecom? Universe-com?). So this problem is entrusted to you!

The input contains multiple queries. The first line contains an integer $T$, the total number of queries. Each query consists of two lines: the first line contains $X$, and the second line contains $N$, asking for the $N$-th smallest palindrome strictly greater than $X$.

For each query, output one line containing the answer.

Constraints: - 20% of the testdata satisfies $X \le 2 \times 10^5$, $N \le 1000$. - 30% of the testdata satisfies $X, N \le 2^{31}-1$ and the answer is no greater than $2^{31}-1$. - 100% of the testdata satisfies $1 \le X, N \le {10}^{10000}$ and the answer is no greater than ${10}^{20001}$, and $1 \le T \le 10$. Translated by ChatGPT 5