using namespace std;

int f( int n)

{

int f_ans = 0 ;

do {

f_ans += n % 10 ;

n /= 10 ;

} while (n != 0 );

return f_ans;

}

int g( int n)

{

int g_ans = 0 ;

do {

g_ans += n % 2 ;

n /= 2 ;

} while (n != 0 );

return g_ans;

}

int main()

{

int T;

cin >> T;

while (T--){

int n;

cin >> n;

int cnt = 0 ;

for ( int i = 1 ; i <= n; i++){

if (f(i) == g(i)){

cnt++;

}

}

cout << cnt << endl;

}

return 0 ;

}