import java.util.*;
import java.math.*;

/**
 * Split the champernowne string into different sections to check. The sections are
 * separated by how many digits are used in consecutive numbers. Brute for the
 * transitions between the sections by constructing the portion of the champernowne
 * string where the given string, s, could span sequences of characters with n digits
 * and sequences with n+1 digits. Then for each run of n digits, try having s start
 * at each of the n possible offsets. Arrange the characters of s in a grid where each
 * row is a number in the champernowne string. For all but the last two columns, try
 * either having the column contain a single value, or two values with a carry somewhere.
 * If there is a carry we know that the rest of the row must be all 9's. This case will
 * then fully determine the rest of the grid, and we can just check for consistency. 
 * If there is not a valid carry case, then we can just choose the smallest value for the
 * column and move onto the next column. Be careful that the first column cannot have a
 * leading 0. 
 * Brute force the last two columns by just trying each possible pair of digits for
 * the first row and use that to determine the rest of the grid.
 * 
 * @author Finn Lidbetter
 */


public class champernowne_finn {
    static BigInteger MINUS_ONE = BigInteger.ZERO.subtract(BigInteger.ONE);
    static long mod = 998_244_353L;
    static int S_MAX = 25;
    static char[] champernowne = new char[9 + 2*(99 - 10 + 1) + 3*(133 - 100 + 1)];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int index = 0;
        for (int i=1; i<=133; i++) {
            char[] number = String.format("%d",i).toCharArray();
            for (char c: number) {
                champernowne[index] = c;
                index++;
            }
        }

        int nTests = Integer.parseInt(sc.nextLine());
        for (int testCase=0; testCase<nTests; testCase++) {
            char[] seq = sc.nextLine().toCharArray();
            System.out.println(solve(seq));
        }
    }
       
    static int brute(char[] seq, char[] other) {
        for (int i=0; i<other.length - seq.length + 1; i++) {
            boolean good = true;
            for (int j=0; j<seq.length; j++) {
                if (seq[j]!='?' && other[i+j]!=seq[j]) {
                    good = false;
                    break;
                }
            }
            if (good) {
                return i;
            }
        }
        return -1;
    }

    static long solve(char[] seq) {
        long bruteIndex = brute(seq, champernowne);
        if (bruteIndex != -1) {
            return bruteIndex + 1;
        }
        BigInteger best = MINUS_ONE;
        for (int digitRun=3; digitRun<=100; digitRun++) {
            // Brute force the transition from `digitRun` to `digitRun+1` digits.
            BigInteger bruteVal = bruteTransition(seq, digitRun);
            best = compare(best, bruteVal);
            for (int offset=0; offset<digitRun; offset++) {
                BigInteger result = solve(seq, digitRun, offset);
                best = compare(best, result);
            }
            if (!best.equals(MINUS_ONE)) {
                break;
            }
        }
        long modded = best.mod(new BigInteger(String.format("%d",mod))).longValue();
        return modded;
    }

    static BigInteger bruteTransition(char[] seq, int digitRun) {
        BruteHelper bruteHelper = buildBrute(digitRun);
        int bruteIndex = brute(seq, bruteHelper.chars);
        if (bruteIndex==-1) {
            return MINUS_ONE;
        }
        //System.out.printf("bruteHelper chars: %s, bruteIndex: %d\n", new String(bruteHelper.chars), bruteIndex);
        BigInteger result = calculateIndex(bruteHelper.vals[bruteIndex], bruteHelper.offsets[bruteIndex]);
        //System.out.printf("bruteHelper val[bruteIndex]: %d, bruteHelper offset[bruteIndex]: %d\n", bruteHelper.vals[bruteIndex], bruteHelper.offsets[bruteIndex]);
        //System.out.printf("Brute transition result: %s\n", result.toString());
        return result;
    }

    static BruteHelper buildBrute(int digits) {
        char[] brute = new char[2*S_MAX];
        BigInteger[] vals = new BigInteger[2*S_MAX];
        int[] offsets = new int[2*S_MAX];
        BigInteger curr = BigInteger.TEN.pow(digits);
        int index = S_MAX;
        while (index<2*S_MAX) {
            int offset = 0;
            for (char c: curr.toString().toCharArray()) {
                brute[index] = c;
                vals[index] = curr;
                offsets[index] = offset;
                index++;
                offset++;
                if (index >= 2*S_MAX) {
                    break;
                }
            }
            curr = curr.add(BigInteger.ONE);
        }
        curr = BigInteger.TEN.pow(digits).subtract(BigInteger.ONE);
        index = S_MAX - 1;
        while (index>=0) {
            char[] digitsArr = curr.toString().toCharArray();
            for (int i=digitsArr.length-1; i>=0; i--) {
                brute[index] = digitsArr[i];
                vals[index] = curr;
                offsets[index] = i;
                index--;
                if (index<0) {
                    break;
                }
            }
            curr = curr.subtract(BigInteger.ONE);
        }
        return new BruteHelper(brute, vals, offsets);
    }


    // Get the index of the first digit of `val` in the champernowne string.
    static BigInteger calculateIndex(BigInteger val, int offset) {
        int numDigits = val.toString().length();
        BigInteger sum = new BigInteger(""+9);
        for (int digits=2; digits<numDigits; digits++) {
            BigInteger terms = BigInteger.TEN.pow(digits).subtract(BigInteger.TEN.pow(digits-1));
            sum = sum.add(terms.multiply(new BigInteger(""+digits)));
        }
        BigInteger lastTerms = val.subtract(BigInteger.TEN.pow(numDigits-1));
        sum = sum.add(lastTerms.multiply(new BigInteger(""+numDigits)));
        return sum.add(new BigInteger(""+(offset+1)));
    }

    // Look for an answer in the section of `digitRun` digits where the first character of `seq` is
    // the `offset`th digit of the `digitRun` digits. 
    static BigInteger solve(char[] seq, int digitRun, int offset) {
        //System.out.printf("digitRun: %d, offset: %d\n", digitRun, offset);
        //System.out.println("Initial puzzle");
        char[][] puzzle = makePuzzle(seq, digitRun, offset);
        //printPuzzle(puzzle);
        char[][] solvedPuzzle = solvePuzzle(puzzle);
        if (solvedPuzzle == null) {
            return MINUS_ONE;
        }
        //System.out.println("Solved puzzle: ");
        //printPuzzle(solvedPuzzle);
        BigInteger val = new BigInteger(new String(solvedPuzzle[0]));
        //System.out.printf("Val: %s, offset: %d\n", val.toString(), offset);
        return calculateIndex(val, offset);
    }

    static char[][] makePuzzle(char[] seq, int digitRun, int offset) {
        int rows = (seq.length+offset) / digitRun;
        if (rows*digitRun<seq.length+offset) {
            rows++;
        }
        // The first row of puzzle will be the first digitRun sequence.
        // puzzle[0][offset] = seq[0];
        // puzzle[1][offset] = seq[0+digitRun];
        // puzzle[0][offset+1] = seq[1];
        char[][] puzzle = new char[rows][digitRun];
        for (int i=0; i<rows*digitRun; i++) {
            int row = i/digitRun;
            int digit = i%digitRun;
            if (i>=offset && i<offset+seq.length) {
                puzzle[row][digit] = seq[i-offset];
            } else {
                puzzle[row][digit] = '?';
            }
        }
        return puzzle;
    }

    static char[][] solvePuzzle(char[][] puzzle) {
        //System.out.println("Before validity check.");
        //printPuzzle(puzzle);
        for (int i=0; i<puzzle[0].length; i++) {
            boolean valid = checkAndFillColumn(puzzle, i);
            if (!valid) {
                //System.out.println("\tInvalid in column " +i);
                return null;
            }
        }
        //System.out.println("After validity check.");
        //printPuzzle(puzzle);
        for (int i=0; i<puzzle.length; i++) {
            if (isRowFull(puzzle, i)) {
                boolean result = checkedFill(puzzle, i, puzzle[i]);
                if (!result) {
                    return null;
                }
                return puzzle;
            }
        }
        boolean validSearch = search(puzzle, 0);
        if (!validSearch) {
            return null;
        }
        return puzzle;
    }

    static boolean propagateColumn(char[][] puzzle, int column, int step) {
        int rows = puzzle.length;
        for (int i=0; i<rows; i++) {
            if (i+step>=rows) {
                break;
            }
            char ch = puzzle[i][column];
            if (ch == '?') {
                continue;
            }
            int val = ch - '0';
            int nextVal = (val+1)%10;
            char nextCh = (char)('0'+nextVal);
            if (puzzle[i+step][column] != '?' && puzzle[i+step][column] != nextCh) {
                return false;
            }
            puzzle[i+step][column] = nextCh;
        }
        for (int i=rows-1; i>=0; i--) {
            if (i-step<0) {
                break;
            }
            char ch = puzzle[i][column];
            if (ch == '?') {
                continue;
            }
            int val = ch - '0';
            int nextVal = (val-1+10)%10;
            char nextCh = (char)('0'+nextVal);
            if (puzzle[i-step][column] != '?' && puzzle[i-step][column] != nextCh) {
                return false;
            }
            puzzle[i-step][column] = nextCh;
        }
        return true;
    }

    static boolean isRowFull(char[][] puzzle, int row) {
        for (int i=0; i<puzzle[row].length; i++) {
            if (puzzle[row][i]=='?') {
                return false;
            }
        }
        return true;
    }

    static boolean checkedFill(char[][] puzzle, int startRow, char[] startRowDigits) {
        for (int i=0; i<puzzle[startRow].length; i++) {
            if (puzzle[startRow][i] != '?' && puzzle[startRow][i]!=startRowDigits[i]) {
                return false;
            }
        }
        BigInteger startRowVal = new BigInteger(new String(startRowDigits));
        int[] directions = {-1,1};
        boolean justCheck = true;
        for (int k=0; k<2; k++) {
            for (int direction: directions) {
                BigInteger val = startRowVal.add(BigInteger.ZERO);
                for (int i=startRow+direction; i<puzzle.length && i>=0; i+=direction) {
                    if (direction == 1) {
                        val = val.add(BigInteger.ONE);
                    } else {
                        val = val.subtract(BigInteger.ONE);
                    }
                    char[] digits = val.toString().toCharArray();
                    if (digits.length!=puzzle[startRow].length) {
                        return false;
                    }
                    for (int j=0;j<digits.length; j++) {
                        if (justCheck) {
                           if (puzzle[i][j]!='?' && puzzle[i][j]!=digits[j]) {
                                return false;
                           }
                        } else {
                            puzzle[i][j] = digits[j];
                        }
                    }
                }
            }
            justCheck = false;
        }
        for (int i=0; i<puzzle[startRow].length; i++) {
            puzzle[startRow][i] = startRowDigits[i];
        }
        return true;
    }

    static boolean search(char[][] puzzle, int column) {
        // Case 0:
        //  We are in the last two columns. Just brute force it...
        // Case 1:
        //  No values defined in the column.
        //      1a:
        //          Fill with 1s or 0s and move onto next column.
        //      1b: 
        //          0/1 fill and carry to 1/2 somewhere. There will be a row like 0/1 999999... somewhere
        // Case 2:
        //  1 value defined in the column.
        //      2a:
        //          Carry before the value.
        //      2b:
        //          Fill with the value.
        //      2c:
        //          Carry after the value.
        // Case 3:
        //  2 values defined in the column.
        //  Carry between those two values. There will be a row like x9999999... somewhere
        for (int i=0; i<puzzle.length; i++) {
            for (int j=0; j<column; j++) {
                if (puzzle[i][j]=='?') {
                    System.out.printf("Error. ? to the left of column %d\n", column);
                    printPuzzle(puzzle);
                    throw new NullPointerException();
                }
            }
        }
        if (column>=puzzle[0].length-2) {
            // Case 0
            int startRow = 0;
            char[] startRowDigits = new char[puzzle[0].length];
            for (int i=0; i<column; i++) {
                startRowDigits[i] = puzzle[0][i];
            }
            if (column==puzzle[0].length-1) {
                for (int i=0; i<10; i++) {
                    startRowDigits[column] = (char)('0' + i);
                    if (checkedFill(puzzle, 0, startRowDigits)) {
                        return true;
                    }
                }
            } else {
                for (int i=0; i<100; i++) {
                    startRowDigits[column] = (char)('0' + (i/10));
                    startRowDigits[column+1] = (char)('0' + (i%10));
                    //System.out.printf("Current column: %d, startRowDigits: %s\n", column, new String(startRowDigits));
                    //printPuzzle(puzzle);
                    if (checkedFill(puzzle, 0, startRowDigits)) {
                        return true;
                    }
                }
            }
            return false;
        }
        int val1 = -1;
        int firstVal1index = -1;
        int lastVal1index = -1;
        int val2 = -1;
        int firstVal2index = -1;
        //System.out.printf("Filling in column %d\n", column);
        //printPuzzle(puzzle);
        for (int i=0; i<puzzle.length; i++) {
            if (puzzle[i][column] != '?') {
                if (val1 == -1) {
                    val1 = puzzle[i][column] - '0';
                    firstVal1index = i;
                    lastVal1index = i;
                } else {
                    if (puzzle[i][column] == (char)('0' + val1)) {
                        lastVal1index = i;
                    } else {
                        if (val2 == -1) {
                            val2 = puzzle[i][column] - '0';
                            firstVal2index = i;
                        } else {
                            if (puzzle[i][column] != (char)('0' + val2)) {
                                //System.out.printf("val1: %d, val2: %d, i=%d, column=%d, puzzle[i][column]=%s\n",val1,val2,i,column,puzzle[i][column]);
                                // This should be impossible.
                                throw new NullPointerException();
                            }
                        }
                    }
                }
            }
        }
        if (val1==-1) {
            for (int i=0; i<puzzle.length; i++) {
                puzzle[i][column] = (column == 0) ? '1' : '0';
            }
            if (search(puzzle, column+1)) {
                return true;
            } else {
                for (int i=0; i<puzzle.length; i++) {
                    puzzle[i][column] = '?';
                }
                char[] startRowDigits = new char[puzzle[0].length];
                for (int i=column+1; i<startRowDigits.length; i++) {
                    startRowDigits[i] = '9';
                }
                startRowDigits[column] = (column == 0) ? '1' : '0';
                for (int startRow=puzzle.length-2; startRow>=0; startRow--) {
                    for (int j=0; j<column; j++) {
                        startRowDigits[j] = puzzle[startRow][j];
                    }
                    if (checkedFill(puzzle, startRow, startRowDigits)) {
                        return true;
                    }
                }
            }
        } else if (val2==-1) {
            char[] startRowDigits = new char[puzzle[0].length];
            for (int j=column+1; j<startRowDigits.length; j++) {
                startRowDigits[j] = '9';
            }
            if (!(column>0 && val1=='0') && !(column==0 && val1=='1')) {
                startRowDigits[column] = (char)('0'+((val1 + 10 - 1) % 10));
                for (int startRow=firstVal1index - 1; startRow>=0; startRow--) {
                    for (int j=0; j<column; j++) {
                        startRowDigits[j] = puzzle[startRow][j];
                    }
                    if (checkedFill(puzzle, startRow, startRowDigits)) {
                        return true;
                    }
                }
            }
            ArrayList<Integer> qIndices = new ArrayList<>();
            for (int i=0; i<puzzle.length; i++) {
                if (puzzle[i][column] == '?') {
                    qIndices.add(i);
                }
                puzzle[i][column] = (char)('0' + val1);
            }
            if (search(puzzle, column+1)) {
                return true;
            }
            for (int i: qIndices) {
                puzzle[i][column] = '?';
            }
            startRowDigits[column] = (char)('0' + val1);
            for (int startRow=puzzle.length-2; startRow>=lastVal1index; startRow--) {
                for (int j=0; j<column; j++) {
                    startRowDigits[j] = puzzle[startRow][j];
                }
                if (checkedFill(puzzle, startRow, startRowDigits)) {
                    return true;
                }
            }
        } else {
            char[] startRowDigits = new char[puzzle[0].length];
            for (int j=column+1; j<startRowDigits.length; j++) {
                startRowDigits[j] = '9';
            }
            startRowDigits[column] = (char)('0' + val1);
            for (int startRow=firstVal2index - 1; startRow>=lastVal1index; startRow--) {
                for (int j=0; j<column; j++) {
                    startRowDigits[j] = puzzle[startRow][j];
                }
                if (checkedFill(puzzle, startRow, startRowDigits)) {
                    return true;
                }
            }
        }
        return false;
    }

    // Check if the puzzle plausibly has a solution. 
    // Fill in values that can be inferred.
    static boolean checkAndFillColumn(char[][] puzzle, int column) {
        if (column==puzzle[0].length-1) {
            return propagateColumn(puzzle, column, 1);
        } else if (column==puzzle[0].length - 2) {
            return propagateColumn(puzzle, column, 10);
        }
        int val1 = -1;
        int val2 = -1;
        for (int i=0; i<puzzle.length; i++) {
            //System.out.printf("\tval1=%d, val2=%s\n",val1,val2);
            if (puzzle[i][column]!='?') {
                if (val1==-1) {
                    val1 = puzzle[i][column] - '0';
                } else {
                    int val = puzzle[i][column] - '0';
                    if (val2==-1 && val == val1) {
                        continue;
                    }
                    if (val2 == -1) {
                        if (val != ((val1 + 1)%10)) {
                            return false;
                        }
                        val2 = val;
                    } else {
                        if (val!=val2) {
                            return false;
                        }
                    }
                }
            }
        }
        if (column==0 && (val1==0 || val2==0)) {
            return false;
        }
        if (val1 != -1 && val2 != -1) {
            boolean placeVal1 = false;
            for (int row = puzzle.length-1; row>=0; row--) {
                if (puzzle[row][column]==(char)('0'+val1)) {
                    placeVal1 = true;
                }
                if (placeVal1) {
                    puzzle[row][column] = (char)('0' + val1);
                }
            }
            boolean placeVal2 = false;
            for (int row=0; row<puzzle.length; row++) {
                if (puzzle[row][column]==(char)('0'+val2)) {
                    placeVal2 = true;
                }
                if (placeVal2) {
                    puzzle[row][column] = (char)('0' + val2);
                }
            }
        }
        return true;
    }


    static BigInteger compare(BigInteger currBest, BigInteger candidate) {
        if (candidate.equals(MINUS_ONE)) {
            return currBest;
        }
        if (currBest.equals(MINUS_ONE)) {
            return candidate;
        }
        if (currBest.compareTo(candidate)<0) {
            return currBest;
        }
        return candidate;
    }
    static void printPuzzle(char[][] puzzle) {
        for (int i=0; i<puzzle.length; i++) {
            System.out.println(new String(puzzle[i]));
        }
        System.out.println();
    }


}
class BruteHelper {
    char[] chars;
    BigInteger[] vals;
    int[] offsets;
    public BruteHelper(char[] bruteArr, BigInteger[] valsArr, int[] offsetsArr) {
        chars = bruteArr;
        vals = valsArr;
        offsets = offsetsArr;
    }
}