import java.util.ArrayList;

import java.util.HashMap;

import java.util.Scanner;

publicclass Main {

    public static void main(String[] args) {

        Solution s = new Solution();

        s.doBefore();

        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        for(int i = 0; i < t; i++) {

            int n = sc.nextInt();

            s.getResult(n);

        }

        sc.close();

    }

}

class Solution {

    public ArrayList<int[]> curResult = new ArrayList<int[]>();

    publicboolean mark = false;

    public void doBefore() {

        int last = 0;

        for(int i = 1; i <= 100000; i++) {

            if(f(i) == g(i)) {

                int[] arr = {i, ++last};

                curResult.add(arr);

            }

        }

    }

    public void getResult(int n) {

        int result = 1;

        for(int i = 0; i < curResult.size(); i++) {

            if(curResult.get(i)[0] <= n) {

                result = curResult.get(i)[1];

            } else

                break;

        }

        System.out.println(result);

    }

//        int curMostClosed = 1;

//        int result = 1; //当前结果是0；

//        

//        if (mark) {

//            for (int k : curResult.keySet()) {

//                if (k > curMostClosed && k <= n) {

//                    curMostClosed = k;

//                }

//            }

//            result = curResult.get(curMostClosed);

//        }

//        mark = true;

//        

//        for(int i = curMostClosed + 1; i <= n; i++) {

//            if(f(i) == g(i))

//                result++;

//        }

//        curResult.put(n, result);

//        

//        System.out.println(result);

//    }

    privateint f(int n ) {

        int result = 0;

        while(n != 0) {

            result += n % 10;

            n /= 10;

        }

        return result;

    }

    privateint g(int n ) {

        int result = 0;

        while(n != 0) {

            result += (n & 1) == 1 ? 1 : 0;

            n >>>= 1;

        }

        return result;

    }