Artem wrote the digit $d$ on the board exactly $n!$ times in a row. So, he got the number $dddddd \dots ddd$ (exactly $n!$ digits).

Now he is curious about which odd digits from $1$ to $9$ divide the number written on the board.

Input

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The next $t$ test cases follow.

Each test case consists of a single line containing two integers $n$ and $d$ ($2 \le n \le 10^9$, $1 \le d \le 9$).

Output

For each test case, output the odd digits in ascending order that divide the number written on the board.

Note

The factorial of a positive integer $n$ ($n!$) is the product of all integers from $1$ to $n$. For example, the factorial of $5$ is $1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$.

Samples

3
2 6
7 1
8 5

1 3 
1 3 7 9 
1 3 5 7 9