굿 모닝!

좋은 아침! 오전 5시 알람이 울렸다. 오늘은 구름이 조금 끼겠고, 오후에는 약한 비가 내리겠다.

방금 잠에서 깬 당신에게 지금 필요한 것은 커피다. 그리고 커피가 더 필요하고, 시리얼도 필요하다. 옷도 입어야 한다. 그리고 또 커피.

따뜻한 시리얼을 만들려고 우유를 전자레인지에 넣고 $k$초 동안 데우려고 한다. 그러려면 전자레인지 키패드로 $k$를 눌러야 한다. 키패드는 이렇게 생겼다.

1 2 3
4 5 6
7 8 9
  0

1부터 9까지는 3행 3열로 놓여 있고, 0은 8 바로 아래에 있다.

아직 커피를 못 마신 탓에 손이, 그리고 눈과 머리가 자꾸 아래로 떨어진다. 그래서 손을 아래쪽이나 오른쪽으로만 옮기면서 숫자를 누를 수 있다. 왼쪽으로 되돌아가거나 위로 올라갈 수는 없다. 대신 같은 키를 다시 누를 수는 있다. 또 누르고, 또 누를 수도 있다.

다시 말해 누른 수를 왼쪽부터 읽었을 때, 이웃한 두 자리의 키 위치는 행도 열도 작아지지 않아야 한다. 예를 들어 180이나 49는 누를 수 있지만, 98이나 132는 누를 수 없다.

이렇게 누를 수 있는 수 중에서 $k$와 가장 가까운 수를 입력한다. 누르는 수는 0 이상의 정수이고, 두 자리 이상이면 맨 앞자리가 0이 아니다. 가장 가까운 수가 두 개면 그중 작은 수를 입력한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 1000$)

이어지는 $T$개의 줄에 각각 정수 $k$가 하나씩 주어진다. ($1 \le k \le 200$)

각 테스트 케이스마다 키패드로 누를 수 있는 수 중 $k$와 가장 가까운 수를 한 줄에 하나씩 출력한다. 가장 가까운 수가 두 개면 작은 쪽을 출력한다.