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