Problem Statement

A string $S$ satisfying all of the following conditions is called a good string. Here, $S_{i}$ denotes the $i$-th character of $S$, and $|S|$ denotes the length of $S$.

• $3\leq |S|$
• $S$ consists of digits
• $S_{1}$ is not 0
• $S_{1}\neq S_{2}$
• $S_{1}\neq S_{|S|}$
• $S_{2}\neq S_{|S|}$
• $S_{2} = S_{3} = \cdots = S_{|S| - 1}$

For example, 167, 93336, and 1000000007 are good strings, while 1221, 09991, and 998244353 are not good strings.

You are given positive integers $N, K$.

Let $U$ be the lexicographically $K$-th smallest string among the good strings of length at most $N + 2$. Find $|U|$, $U_{1}, U_{2}, U_{|U|}$. It can be shown from the constraints that such a string $U$ exists.

You are given $T$ test cases; solve each of them.

Constraints

• $1\leq T\leq 10^{5}$
• $1\leq N\leq 2\times 10^{9}$
• $1\leq K\leq 648N$
• All input values are integers

Input

$T$
$case_{1}$
$case_{2}$
$\ldots$
$case_{T}$

Here, $case_{i}$ represents the $i$-th test case, given in the following format.

$N$ $K$

Output

Print $T$ lines.

On the $i$-th line, print the answer to $case_{i}$ in the following format, separated by spaces.

$|U|$ $U_{1}$ $U_{2}$ $U_{|U|}$

Sample

3
10 22
167 924
924924 167167167

10 1 0 7
54 1 0 5
754715 3 5 8