import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
publicclass Main {
public static void main(String[] args) {
Solution s = new Solution();
s.doBefore();
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for(int i = 0; i < t; i++) {
int n = sc.nextInt();
s.getResult(n);
}
sc.close();
}
}
class Solution {
public ArrayList<int[]> curResult = new ArrayList<int[]>();
publicboolean mark = false;
public void doBefore() {
int last = 0;
for(int i = 1; i <= 100000; i++) {
if(f(i) == g(i)) {
int[] arr = {i, ++last};
curResult.add(arr);
}
}
}
public void getResult(int n) {
int result = 1;
for(int i = 0; i < curResult.size(); i++) {
if(curResult.get(i)[0] <= n) {
result = curResult.get(i)[1];
} else
break;
}
System.out.println(result);
}
// int curMostClosed = 1;
// int result = 1; //当前结果是0;
//
// if (mark) {
// for (int k : curResult.keySet()) {
// if (k > curMostClosed && k <= n) {
// curMostClosed = k;
// }
// }
// result = curResult.get(curMostClosed);
// }
// mark = true;
//
// for(int i = curMostClosed + 1; i <= n; i++) {
// if(f(i) == g(i))
// result++;
// }
// curResult.put(n, result);
//
// System.out.println(result);
// }
privateint f(int n ) {
int result = 0;
while(n != 0) {
result += n % 10;
n /= 10;
}
return result;
}
privateint g(int n ) {
int result = 0;
while(n != 0) {
result += (n & 1) == 1 ? 1 : 0;
n >>>= 1;
}
return result;
}