Colin is designing a special calendar using two cubes.

Each cube has exactly 6 faces, and each face is labeled with a digit from 0 to 8. Using the two cubes, Colin wants to display dates in two-digit format.

For example, the illustration above shows two cubes displaying the integer 16 on the front. One cube shows the digit 1, and the other shows the digit 6.

To display an integer $d \in [01, 99]$ in two-digit format, choose one cube to show the tens digit (for 01 to 09, the tens digit is 0), and the other should show the units digit. Note that the digit 6 can also represent 9. That is, if a cube has a 6, it can be used as either 6 or 9.

Given two cubes, we define their MEX as the smallest positive integer in two-digit format that cannot be displayed. It can be shown that no two cubes can display all integers from 01 to 99 (both inclusive).

Given an integer $x$ (given in two-digit format), you need to construct two cubes such that their MEX is exactly $x$.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 99$), indicating the number of test cases. For each test case:

The only line contains an integer $x$ ($01 \le x \le 99$) in two-digit format.

Output

For each test case:

• If it is possible to construct two cubes such that their MEX is exactly $x$, first output Yes in one line. Then output a second line containing 12 integers (from 0 to 8) separated by a space, indicating the two cubes. The first 6 integers are the digits on the first cube, while the last 6 integers are the digits on the second cube.
• Otherwise, if it is impossible to do so, just output No in one line.

Example

Input 1

4
01
02
99
11

Output 1

Yes
0 0 0 0 0 0 0 0 0 0 0 0
Yes
1 1 1 1 1 1 0 0 0 0 0 0
No
Yes
4 0 5 7 6 8 0 2 3 1 0 0