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;

    }

    

}
这是幸运数那道题,打注释的是我一开始写的方法,后来发现本地运行是可以的,但是OJ说是运行时错误,于是开始使劲想,发现其实输入大小不是很大,于是直接预处理搞了100000个数。结果这样就AC了