import java.util.*;
public class Main{
	
	public static int f(int n){
		int result = 0;
		while(n!=0){
			result += (n%10);
			n /= 10;
		}
		return result;
	}
	
	public static int g(int n){
		int result = 0;
		while(n!=0){
			result += (n%2);
			n /= 2;
		}
		return result;
	}
	
    public static void main(String[] args){
    	int[] aa = new int[100005];
    	int bb = 0;
    	for(int i=1;i<aa.length;i++){
    		if(f(i)==g(i)){
    			bb++;
    		}
    		aa[i]=bb;
    	}
    	Scanner scanner = new Scanner(System.in);
    	int t = scanner.nextInt();
    	for(int i=0;i<t;i++){
    		int n = scanner.nextInt();
    		/*int count = 0;
    		for(int j=1;j<=n;j++){
    			if(f(j)==g(j)){
    				count++;
    			}
    		}*/
    		System.out.println(aa[n]);
    	}
    }
}

ac