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

public class 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[]>();
//    public boolean 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);
//    }
    
    private int f(int n ) {
        int result = 0;
        while(n != 0) {
            result += n % 10;
            n /= 10;
        }
        return result;
    }
    
    private int g(int n ) {
        int result = 0;
        while(n != 0) {
            result += (n & 1) == 1 ? 1 : 0;
            n >>>= 1;
        }
        return result;
    }
    
}