Numeric Keypad

类似数位dp的做法，先预处理出每一位数字可达的所有数字，然后从大到小从高位向地位枚举

#include<bits/stdc++.h>
using namespace std;
using ll = int64_t;
using pii = pair<int,int>;
vector<vector<int>> e(10),b;
inline void init(){
    e[1] = (vector<int>({9,8,7,6,5,4,3,2,1,0}));
    e[2] = (vector<int>({9,8,6,5,3,2,0}));
    e[3] = (vector<int>({9,6,3}));
    e[4] = (vector<int>({9,8,7,6,5,4,0}));
    e[5] = (vector<int>({9,8,6,0}));
    e[6] = (vector<int>({9,6}));
    e[7] = (vector<int>({9,8,7,0}));
    e[8] = (vector<int>({9,8,0}));
    e[9] = (vector<int>({9}));
    e[0] = (vector<int>({0}));
}

void solve(){

    string s;
    cin>>s;
    int n = s.size();
    bool f = false;
    string res;
    auto dfs = [&](auto &&self, int pos, int now, bool limit, string tp) -> void{
        if(pos==-1){
            f = true;
            res = tp;
            return;
        }
        int up = limit ? s[n-pos-1]-'0' : 9;
        for(auto v:e[now]){
            if(v>up) continue;
            self(self, pos-1, v, limit&&v==up, tp+to_string(v));
            if(f) return;
        }
        return;
    };
    for(int i=s[0]-'0';i>=0;--i){
        dfs(dfs, n-2, i, i==s[0]-'0', to_string(i));
        // cout<<f<<"\n";
        if(f) break;
    }
    cout<<res<<'\n';
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int _ = 1;
    cin>>_;
    while(_--){
        init();
        solve();

    }

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

void locate(int d,int &x,int &y)
{     d = d?--d:10;     x = d/3;     y = d%3;
}

bool reach(int x,int y) 
{     int x1,y1,x2,y2;     locate(x-'0',x1,y1);     locate(y-'0',x2,y2);     return x1<=x2 && y1<=y2;     }


int main()
{     int T;     cin>>T;     while(T--)     {         string k;         cin>>k;         for(int i=0;i<k.size()-1;i++)         {             while(!reach(k[i],k[i+1]))             {                 if(--k[i+1]<0)                     k[i--]--;                 for(int j=i+2;j<k.size();j++)                     k[j] = '9';             }         }         cout<<k<<endl;     }     return 0;
}

	

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        HashMap<Integer, Integer[]> map = getMap();
        s.nextInt();
        while (s.hasNext()) {
            Integer[] ints = parseString(s.next());
            Stack<Integer> l = new Stack<>();
            constructString(ints, 0, map, l, false);

            StringBuilder sb = new StringBuilder();
            for (Integer c : l) {
                sb.append(c);
            }
            System.out.println(sb);
        }
    }

    private static boolean constructString(Integer[] s, int i, HashMap<Integer, Integer[]> map, Stack<Integer> l, boolean flag) {
        if (l.size() == 0) {
            l.push(s[i]);
            if (constructString(s, i + 1, map, l, false)) {
                return true;
            }
            l.set(0, l.peek() - 1);
            return constructString(s, i + 1, map, l, true);
        }
        if (i == s.length)
            return true;
        if (flag) {
            Integer[] q = map.get(l.peek());
            l.push(q[q.length - 1]);
            return constructString(s, i + 1, map, l, flag);
        }

        Integer j = 0, B[] = map.get(l.peek());
        for (; j < B.length; j++) {
            if (B[j] > s[i])
                break;
        }
        for (j--; j > -1; j--) {
            l.push(B[j]);
            if (B[j] < s[i])
                flag = true;
            if (constructString(s, i + 1, map, l, flag))
                return true;
            l.pop();
        }
        return false;
    }

    public static Integer[] parseString(String s) {
        Integer[] ints = new Integer[s.length()];
        for (int i = 0; i < s.length(); i++) {
            ints[i] = s.charAt(i) - 48;
        }
        return ints;
    }

    public static HashMap<Integer, Integer[]> getMap() {
        Integer A[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        HashMap<Integer, Integer[]> map = new HashMap<>();
        LinkedList<Integer> l = new LinkedList<>();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int x = i; x < 3; x++) {
                    for (int y = j; y < 3; y++) {
                        l.add(A[x][y]);
                    }
                }
                if (j <= 1) {
                    l.addFirst(0);
                }
                map.put(A[i][j], l.toArray(new Integer[0]));
                l.clear();
            }
        }
        map.put(0, new Integer[]{0});
        return map;
    }
}

package com.neil.java;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

import org.junit.Test;


public class PhoneNum {
	// 按照下面的排序，返回数组的位置
	/**
	 * 1 2 3 
	 * 4 5 6 
	 * 7 8 9 
	 *   0
	 * 
	 * @param digit
	 * @return
	 */
	static Point locate(int digit) {
		int x = 0, y = 0;
		digit = digit > 0 ? --digit : 10;// 如果是0，则认为其所在的位置是10，其他的都是数字-1,
		x = digit / 3; // 行数
		y = digit % 3; // 列数
		return new Point(x, y);
	}
	/**
	 * 将字符串变成int数组
	 * @param numString 字符串
	 * @return 返回int数组
	 */
	public static int[] stringToIntArray(String numString)
	{
		int [] ret = new int[numString.length()];
		for (int i = 0; i < numString.toCharArray().length; i++) {
			ret[i] = Integer.parseInt(numString.toCharArray()[i]+"");
		}
		return ret;
	}
	
	/**
	 * 将int数组编程字符串输出
	 * @param numArray int数组
	 * @return 返回字符串
	 */
	public static String intArrayToString(int [] numArray)
	{
		StringBuilder ret = new StringBuilder();
		for (int i = 0; i < numArray.length; i++) {
			ret.append(numArray[i]);
		}
		return ret.toString();
	}
	
	/**
	 * 根据题意，我们只能向右，向下走。 因此，第一个数字在键盘矩阵中的位置坐标(x1,y1),第二个数字在键盘矩阵中的位置坐标(x2,y2)
	 * 需要满足x1<=x2&&y1<=y2;
	 * 
	 * @param x
	 *            键盘上的数字1
	 * @param y
	 *            键盘上的数组2
	 * @return 如果可以到达，返回true，反之，返回false
	 */
	static boolean reach(int x, int y) // 判断x能否到达y
	{
		Point pointX = locate(x); // 获取x的行 列
		Point pointY = locate(y); // 获取y的行 列
		return pointX.x <= pointY.x && pointX.y <= pointY.y;
	}

	public static void main(String[] args) {
		int T;
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt();
		List<String> list = new ArrayList<String>();
		for (; T-- > 0;) {
			int[] indexNum = stringToIntArray(scanner.next());
			
			for (int i = 0; i < indexNum.length - 1; i++) // 因为后面有i+1操作，这里不能<length
			{
				// 如果第i（从左向右递增）位上的数字能够连接第i+1位上的数字，则继续判断i+1和i+2是否可达，如果都可打，则直接输出
				while (!reach(indexNum[i], indexNum[i + 1])) {
					if (--indexNum[i + 1] < 0)
						indexNum[i--]--;
					for (int j = i + 2; j < indexNum.length; j++)
						indexNum[j] = 9;
					//处理i=-1的情况
					if(i==-1)
						i=0;
				}
			}
			//添加到list中，集中打印
			list.add(intArrayToString(indexNum));
		}
		scanner.close();
		for (String string : list) {
			System.out.println(string);
		}
	}

	//测试获取键盘9的位置
	@Test
	public void testLocate() {
		System.out.println(locate(9));
	}

	//测试两个数字是不是可以到达
	@Test
	public void testReach() {
		System.out.println(reach(8, 9));
	}
	
	//char和int互转
	@Test
	public void testCharToInt() {
		System.out.println(Integer.parseInt('9' + ""));
		System.out.println(String.valueOf(9).charAt(0));
	}

}
//坐标类
class Point {
	public int x;
	public int y;

	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}

	public String toString() {
		return "(x,y)=(" + x + "," + y + ")";
	}
}

#include <bits/stdc++.h>
vector<vector<char>> phone = {{'0'},
                              {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'},
                              {'0', '2', '3', '5', '6', '8', '9' },
                              {'3', '6', '9'},
                              {'0', '4', '5', '6', '7', '8', '9'},
                              {'0', '5', '6', '8', '9'},
                              {'6', '9'},
                              {'0', '7', '8', '9'},
                              {'0', '8', '9'},
                              {'9'}};

void solve(int i, string& s, vector<char>& res) {
    if (i >= s.size()) return;
    if (i == s.size()-1) {
        res.push_back(s[i]);
        return;
    }
    int line = s[i] - '0';
    if (find(phone[line].begin(), phone[line].end(), s[i+1]) != phone[line].end()) {
        res.push_back(s[i]);
        solve(i+1, s, res);
    }else {
        int k = static_cast<int> (phone[line].size()-1);
        while (phone[line][k] > s[i+1] && k >= 0) k--;
        if (k >= 0) {
            res.push_back(s[i]);
            res.push_back(phone[line][k]);
            for (++i; i < s.size()-1; ++i) res.push_back(*(phone[phone[line][k]-'0'].end()-1));
            return;
        }else {
            while (i >= 0) {
                s[i]--;
                if (i == 0) {
                    res.push_back(s[i]);
                    for (int j = 0; j < s.size() - 1; ++j) {
                        res.push_back(*(phone[s[i]-'0'].end()-1));
                    }
                    return;
                }
                else if (find(phone[s[i-1]-'0'].begin(), phone[s[i-1]-'0'].end(), s[i]) != phone[line].end()) {
                    res.push_back(s[i]);
                    for (int j = i+1; j < s.size(); ++j) {
                        res.push_back(*(phone[s[i]-'0'].end()-1));
                    }
                    return;
                }else {
                    res.pop_back();
                    i--;
                }
            }
        }
    }
}

int main() {
    int T;
    cin >> T;
    for(int m = 0; m < T; ++m) {
        string s;
        cin >> s;
        vector<char> res;
        solve(0, s, res);
        for(auto &item : res)
            cout << item;
        cout << endl;
    }
    return 0;
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int count = scan.nextInt();
		scan.nextLine();
		String[] array = new String[count];
		for (int i = 0; i < count; i++) {
			array[i] = scan.nextLine();
		}

		int[] niubi = { 00, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 25, 26, 28, 29, 33, 36, 39, 40, 44, 45,
				46, 47, 48, 49, 50, 55, 56, 58, 59, 66, 69, 70, 77, 78, 79, 80, 88, 89, 99 };

		for (String arrayi : array) {

			char[] num = arrayi.toCharArray();
			for (int i = 0; i < num.length - 1;) {
				char a = num[i];

				char b = num[i + 1];
				int tem = Integer.parseInt(("" + a + b));

				if (Arrays.binarySearch(niubi, tem) >= 0) {
					// System.out.println("okkkkkkkkk"+tem);
					i++;
				} else {
					// System.out.println("***kkkkk"+tem);
					int wtf = 0;
					for (int *** : niubi) {
						if (*** <= tem) {
							wtf = ***;
						} else {
							break;
						}
					}
					num[i] = (char) (wtf / 10 + 48);
					num[i + 1] = (char) (wtf % 10 + 48);
					for (int **** = i + 2; **** < num.length; ****++) {
						if (num[i] == '0')
							num[****] = '0';
						else
							num[****] = '9';
					}
					i = (i - 1) >= 0 ? i - 1 : 0;
				}

			}
			System.out.println(String.valueOf(num));

		}
	};
}

先建表，列表示前一个数字，行表示后一个数字。
1 表示对应行的数字后面可以跟对应列的数字，0 则相反。

#include<iostream>
#include<string.h>

using namespace std;

void subtrc(char a[],int k){//剪枝，从位置k开始修改数字，而不是从末尾开始每次只减少1
    int jw;//借位
    jw = -1;
    for(int i=k; i>=0&&jw!=0; i--){
        if(a[i]-'0'>0){
            a[i] += jw;
            jw = 0;
        }
        else{
            a[i] = '9';
            jw = -1;
        }
        for(int j=i+1;j<strlen(a);j++)//只要修改了还没到末尾数字，都需要将后面的置为9
            a[j] = '9';
    }
}

int main(){
    char chk[10][10]={
    {1,0,0,0,0,0,0,0,0,0},
    {1,1,1,1,1,1,1,1,1,1},
    {1,0,1,1,0,1,1,0,1,1},
    {0,0,0,1,0,0,1,0,0,1},
    {1,0,0,0,1,1,1,1,1,1},
    {1,0,0,0,0,1,1,0,1,1},
    {0,0,0,0,0,0,1,0,0,1},
    {1,0,0,0,0,0,0,1,1,1},
    {1,0,0,0,0,0,0,0,1,1},
    {0,0,0,0,0,0,0,0,0,1}
    };

    int t;
    char a[502];
    int p,r;
    int i,j;
    cin>>t;
    for(i=0;i<t;i++){
        cin>>a;
        while(1){
            for(j=1;j<strlen(a);j++){
                p = a[j-1]-'0';//获取前一个数字
                r = a[j]-'0';//获取当前数字
                if(chk[p][r]!=1)//查表，不满足条件
                    break;
            }
            if(j<strlen(a)){
                subtrc(a,j);
	    }
            else{
                cout<<a<<endl;
                break;
            }
        }
    }
}

[9][9][0]     //[0]不合法，且没有小于[0]的按键，回溯到第一次按[9]时

到此，我们可以总结出一套算法：

1、从高位开始（数字的高位，数组中的低位，按字符串储存的话）；

2、从不大于当前数位的合法按键中从大到小枚举，

若有合法按键存在且等于当前数位，跳到下一位，重复2；

若没有，则回溯；

若小于当前数位，那么后面的所以数位则填充当前最大的合法值，结束；

#include <iostream>
using namespace std;
void locate(int digit,int &x,int &y)
{
    digit=digit?--digit:10;
    x=digit/3;  //行数
    y=digit%3;  //列数
}
bool reach(int x,int y)   //判断x能否到达y
{
    int x0,y0,x1,y1;
    locate(x-'0',x0,y0);  //获取x的行 列
    locate(y-'0',x1,y1);  //获取y的行 列
    return x0<=x1&&y0<=y1;
}
int main()
{
    int T;
    for(cin>>T;T--;)
    {
        string K;
        cin>>K;
        for(int i=0;i<K.size()-1;i++) //个位不用参加循环
        {
            while(!reach(K[i],K[i+1]))
            {
                if(--K[i+1]<0)
                    K[i--]--;
                for(int j=i+2;j<K.size();j++)
                    K[j]='9';
            }
        }
        cout<<K<<endl;
    }
}

// 主要是中间位为0的处理，采用从低位到高位可避免向高位借位的麻烦。
#include<iostream>
#include<string>
#include<vector>
using namespace std;

const vector<string> helper = { "0", "0123456789", "0235689", "369",
"0456789", "05689", "69", "0789", "089", "9" };
int main(){
	int num;
	while (cin >> num){
		vector<string> vStr(num);
		for (int i = 0; i < num; ++i){
			cin >> vStr[i];
		}
		for (string str : vStr){
			for (int i = str.size() - 2; i >= 0; --i){ // 逆序（低位->高位
				while (helper[str[i] - '0'].find(str[i + 1]) == -1){					
					if (str[i + 1] == '0'){
						str[i]--;
						str[i + 1] = '9';
					}else
						str[i + 1]--;                    
                    for (int j = i + 2; j < str.size(); ++j)
                        str[j] = '9';
				}
                if(str[i+1] == '0'){ //这点是因为后置位都变为9，而0后面只可跟0
                    for (int j = i + 1; j < str.size(); ++j)
                        str[j] = '0';
                }
			}
			cout << str << endl;
		}
	}
	return 0;
}

// 借鉴 Glenn_Gould 方法，从高位到低位
#include<iostream>
#include<string>
#include<vector>
using namespace std;

const vector<string> helper = { "0", "0123456789", "0235689", "369",
"0456789", "05689", "69", "0789", "089", "9" };
int main(){
	int num;
	while (cin >> num){
		vector<string> vStr(num);
		for (int i = 0; i < num; ++i){
			cin >> vStr[i];
		}
		for (string str : vStr){
			for (int i = 0; i < str.size() - 1; ++i){ // 正序
				while (helper[str[i] - '0'].find(str[i + 1]) == -1){					
					if (str[i + 1]-- == '0'){
						str[i--]--;
					}
					for (int j = i + 2; j < str.size(); ++j)
						str[j] = '9';
					if (i < 0) // 当i--到最高位时避免越界，也可理解为再一次循环检查
						i++;
				}
			}
			cout << str << endl;
		}
	}
	return 0;
}

//根据别人思路写的、发现最难的是容易把pad和last数组写错/(ㄒoㄒ)/~~
#include<iostream>
#include<string>
using namespace std;
int pad[10][10]={
    {0},
    {0,1,2,3,4,5,6,7,8,9},
    {0,2,3,5,6,8,9},
    {3,6,9},
    {0,4,5,6,7,8,9},
    {0,5,6,8,9},
    {6,9},
    {0,7,8,9},
    {0,8,9},
    {9,}

};
int last[]={0,9,6,2,6,4,1,3,2,0};
string num;
int n;
bool st;
bool test(int index,int n){
    for(int i=index;i<num.size();i++){
        int ts=num[i]-'0';

        if(n==ts){
            n=pad[n][0];
            continue;
        }else if(n<ts){
            return true;
        }else{
            return false;
        }
    }
    return true;
}
int main(){
    //如果非st就尽量大
    //如果st就看后面最小的能不能满足
    int t;
    cin>>t;
    while(t--){
      cin>>num;
      int n=num.size();
      st=true;
      string ans;
      int now=1;
      for(int i=0;i<num.size();i++){
          int ts=num[i]-'0';
          if(st){
              for(int j=last[now];j>=0;j--){
                  if(pad[now][j]>ts){
                      continue;
                  }else if(pad[now][j]==ts){
                      if(test(i,pad[now][j])){
                          now=pad[now][j];
                      }else{
                         st=false;
                      	 now=pad[now][j-1];
                      }
                  }else{
                      st=false;
                      now=pad[now][j];
                  }
                  ans+='0'+now;;
                  break;
              }
          }else{
              ans+=(char)('0'+pad[now][last[now]]);
              now=pad[now][last[now]];
          }
      }
        cout<<ans<<endl;
    }

}

lst = [None for i in range(10)]
lst[0]=['0']
lst[1]=['0','1','2','3','4','5','6','7','8','9']
lst[2]=['0','2','3','5','6','8','9']
lst[3]=['3','6','9']
lst[4]=['0','4','5','7','6','8','9']
lst[5]=['0','5','6','8','9']
lst[6]=['6','9']
lst[7]=['0','7','8','9']
lst[8]=['0','8','9']
lst[9]=['9']
lst[0]=['0']
n = input()
n = int(n)
for i in range(n):
    nu = input()
    num = []
    for i in nu:
        num.append(i)
    index = -1
    for i in range(len(num)-1):
        if num[i+1] not in lst[int(num[i])]:
            if num[i+1]>=min(lst[int(num[i])]):
                for k in range(len(lst[int(num[i])])):
                    if lst[int(num[i])][k]>num[i+1]:
                        break
                num[i+1]=lst[int(num[i])][k-1]
                index = i+2
                break
            else:
                te = str(num[i])
                if num[i]!='9' and i>0:
                    num[i] = lst[int(num[i-1])][lst[int(num[i-1])].index(te)-1]
                    index = i+1
                    break
                elif num[i]=='9' and i>0:
                    te = int(i)-1
                    while te>=0 and num[te]=='9':
                        te-=1
                    num[te+1] = str(8)
                    index=te+2
                    break
                elif i==0:
                    num[0] = str(int(num[0])-1)
                    index=1
                    break
    if index!=-1:
        for j in range(index,len(num)):
            num[j] = max(lst[int(num[j-1])])
    out = ''
    for i in num:
        out+=i
    print(out)

x = [10]*10
x[0]=[0]
x[1]=[1,2,3,4,5,6,7,8,9,0]
x[2]=[2,3,5,6,8,9,0]
x[3]=[3,6,9]
x[4]=[4,5,6,7,8,9,0]
x[5]=[5,6,8,9,0]
x[6]=[6,9]
x[7]=[7,8,9,0]
x[8]=[8,9,0]
x[9]=[9]

T=int(input())
for t in range(T):
    K=list(input())
    for i in range(len(K)-1):
        while int(K[len(K)-1-i]) not in x[int(K[len(K)-2-i])]:#从低位往高位遍历
            if K[len(K)-i-1] == '0':#低位等于0且不在高位的下一步中
                K[len(K)-i-2] = str(int(K[len(K)-i-2])-1)#高位数字-1
                K[len(K)-i-1] = '9'#低位为9
            else:#低位不为0
                K[len(K)-i-1] = str(int(K[len(K)-1-i]) -1)#低位-1
            if len(K)-i < len(K):#当低位不是最后一位时
                for j in range(len(K)-i,len(K)):#要么这一位减了1,要么前一位减了1
                    K[j] = '9'#后面全部的变成 9才能最接近给的数字
        if K[len(K)-i-1] =='0' :#低位在高位的下一步中且低位为0
            if len(K)-i < len(K):#不是最后一位
                for j in range(len(K)-i,len(K)):#0后面只能是0
                    K[j] = '0'
    print(''.join(K))

import java.util.Scanner;
public class Main{
    public static String[] dp={ "0", "0123456789", "0235689", "369","0456789", "05689", "69", "0789", "089", "9" };
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int t = input.nextInt();
        input.nextLine();
        while(t-->0){
            String result="",s=input.nextLine();
            boolean flag=false;
            int i=0;
            for(;i<s.length()-1;i++){
                if(judge(s.charAt(i),s.charAt(i+1))){
                    result+=s.charAt(i);
                }else{
                    flag=true;
                    break;
                }
            }
            if(flag){
                while(i>=0&&less(s.charAt(i),s.charAt(i+1)).equals("")){
                    //System.out.println("work");
                    if(i==0){
                        result=String.valueOf(((int)s.charAt(i)-48-1));
                        while(i++<s.length()-1){
                            int l=dp[(int)result.charAt(0)-48].length();
                            result+=dp[(int)result.charAt(0)-48].charAt(l-1);
                        }
                        break;
                    }
                    i--;
                    result=result.substring(0,result.length()-1);
                }
                if(i<s.length()){
                    String p=less(s.charAt(i),s.charAt(i+1));
                    result+=s.charAt(i++);
                    result+=p;
                    while(i++<s.length()-1){
                        int l=dp[Integer.parseInt(p)].length();
                        result+=dp[Integer.parseInt(p)].charAt(l-1);
                    }
                }
            }else{
                result+=s.substring(s.length()-1, s.length());
            }
            System.out.println(result);
        }
    }
    public static boolean judge(char a,char b){
        if(dp[(int)a-48].contains(String.valueOf(b))) return true;
        else return false;
    }
    public static String less(char a,char b){
        int index=-1;
        int temp=(int)b-48;
        while(index<0&&temp>=0){
            index=dp[(int)a-48].indexOf(String.valueOf(--temp));
        }
        if(index<0) 
            return "";
        else
            return String.valueOf(dp[(int)a-48].charAt(index));
    }
}

/*bfs + 优先队列*/
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<vector>
#include<math.h>
#include<map>
#include<queue>
using namespace std;
bool check(char c, char nc){
    switch(c){
        case '1':
            return true;
            break;
        case '2':
            if(nc == '1' || nc == '4' || nc == '7') return false;
            return true;
            break;
        case '3':
            if(nc == '3' || nc == '6' || nc == '9') return true;
            return false;
            break;
        case '4':
            if(nc == '1' || nc == '2' || nc == '3') return false;
            return true;
            break;
        case '5':
            if(nc == '5' || nc == '6' || nc == '8' ||nc == '9' || nc == '0') return true;
            return false;
            break;
        case '6':
            if(nc == '6' || nc == '9') return true;
            return false;
            break;
        case '7':
            if(nc == '7' || nc == '8' || nc == '9' || nc == '0') return true;
            return false;
            break;
        case '8':
            if(nc == '8' || nc == '9' || nc == '0') return true;
            return false;
            break;
        case '9':
            if(nc == '9') return true;
            return false;
            break;
        case '0':
            if(nc == '0') return true;
            return false;
            break;
    }
    return false;
}
int main(){
    //freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        string s;
        cin>>s;
        priority_queue<string> q;
        string p = "0123456789";
        for(int i=0;i<p.length();i++){
            if(check('1', p[i])){
                string tmp = "";
                tmp += p[i];
                q.push(tmp);
            }
        }
        while(!q.empty()){
            string top = q.top();
            q.pop();
            if(top.length() >= s.length()){
                cout<<top;
                break;
            }
            char back = top.back();
            for(int i=0;i<p.length();i++){
                if(check(back, p[i])){
                    string tmp = top + p[i];
                    if(tmp > s) continue;
                    q.push(tmp);
                }
            }
        }
        cout<<endl;
    }
    return 0;
}