import java.util.Scanner;

public class Main {
   public static void main(String args[])
    {
    	boolean[] B = new boolean[100000 + 1];
    	for (int i = 1; i < 100000 + 1; i++) {
    		int binary =g(i);  		
    		int ten = f(i);
    		if (binary == ten) 
    			B[i] = true;
    	}
    	
        Scanner cin = new Scanner(System.in);
        int times = cin.nextInt();
        for (int i = 0; i < times; i++) {
        	int n = cin.nextInt();
        	int count = 0;
        	for (int j = 1; j <= n; j++) {{
        		if (B[j])
        			count++;
        		}
        	}
        	System.out.println(count);
        }
        
        
    }
	private static int f(int num){
		String str = String.valueOf(num);
		int sum = 0;
		for(int i = str.length() - 1;i>=0;i--){
			sum+=Integer.valueOf(str.charAt(i)+"");
		}
		return sum;
	}
	private static int g(int num){
		String str = Integer.toBinaryString(num);
		int sum  = 0;
		for(int i = 0;i<str.length();i++){
			sum+=Integer.valueOf(str.charAt(i)+"");
		}
		return sum;
	}

}