Good morning!

Interview

Time limit1sMemory limit256 MB

Summary

Find the nonnegative integer closest to k whose consecutive keypad digits never move up or left, breaking ties toward the smaller number.

Level: Easy3 of 10
Topics: Brute force, Implementation
Solved: No attempts yet

Problem

Good morning! This is your 5 a.m. wake-up call. A partly cloudy day is coming, with light rain in the afternoon.

You have just woken up. You desperately need coffee. And more coffee. And some cereal. And your clothes. And coffee.

To make warm cereal you put some milk in the microwave and heat it for $k$ seconds. That means typing $k$ on the microwave keypad, which looks like this:

The digits 1 to 9 sit in 3 rows and 3 columns, and 0 sits directly below 8.

You still have not had your coffee, so your hand keeps falling down, and so do your eyes and your brain. You can only type a number while your hand moves down or to the right. You cannot go back left and you cannot move your hand up, though you can press the same key again. And again. And again.

In other words, read the typed number from the left: between two neighbouring digits, neither the row nor the column of the key may decrease. You can type 180 or 49, but not 98 or 132.

Type the number closest to $k$ among the numbers you can type. The number you type is a nonnegative integer, and a number of two or more digits does not start with 0. If two numbers are equally close, type the smaller one.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 1000$ ).

Each of the next $T$ lines contains one integer $k$ ( $1 \le k \le 200$ ).

Output

For each test case, print on its own line the number closest to $k$ that can be typed on the keypad. If two numbers are equally close, print the smaller one.

Examples2

Example 1
Input
```
3
180
83
132
```
Expected output
```
180
80
133
```
Example 2
Input
```
2
1
200
```
Expected output
```
1
200
```