Description

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!

Input Format

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$.

Output Format

For each query, output one line containing the answer.

3
1
1
17
2
98
2

2
33
101

Hint

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