363. The Leap Code

0

Medium

Martin's professor taught him about gray codes, hamming, and unit distances. He also introduced him to leap codes, which are numbers where each adjacent digit differs by 1. For example, 3456 and 9878 are leap codes. It is known that all one-digit numbers are leap codes. Given a number N, find all the leap codes less than or equal to N.

Input Format

The first line contains the number of test cases, T. Then T test cases follow. Each test case consists of a positive number N.

Output Format

For each test case, print all the leap codes less than or equal to N in a new line.

Example

Input

1
50

Output

0 1 2 3 4 5 6 7 8 9 10 12 21 23 32 34 43 45

Constraints

1 <= T <= 100
1 <= N <= 10

^{9}Loading...

View Submissions

Console