package ojtest; import java.util.Scanner; public class Jd2 { int[] dp=new int[100001]; int index=1; public int f(int n){ int sum=0; while(n!=0){ sum+=n%10; n=n/10; } return sum; } public int g(int n){ int sum=0; while(n!=0){ sum+=n&1; n>>>=1; } return sum; } public int countNumber(int n){ if(index>n) return dp[n]; for(;index<=n;index++) { dp[index]=dp[index-1]; if(f(index)==g(index)){ dp[index]++; } } return dp[n]; } public static void main(String[] args) { Jd2 test=new Jd2(); Scanner input=new Scanner(System.in); int N=input.nextInt(),n; for(int i=1;i<=N;i++){ n=input.nextInt(); System.out.println(test.countNumber(n)); } } }