Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

B. Digits
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Artem wrote the digit d on the board exactly n! times in a row. So, he got the number ddddddddd (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 (1t100) — 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 (2n109, 1d9).

Output

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

Example
Input
3
2 6
7 1
8 5
Output
1 3 
1 3 7 9 
1 3 5 7 9 
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 12345=120.