方法1：暴力

暴力的思路就是每次读个 $ n $ ，然后双重循环暴力地查找所有可能性。

但是这道题如果用暴力仿佛不太行...如果使用暴力就是 $ O(n^3) $ 的时间复杂度面对 $ 10^6 $ 的数据，不爆就神了。

方法2：回溯

回溯的思路就是每次记录下 $ 0 $ 的个数以及当前数字的位数。我们用$ zero count$记录下当前的0的个数。如果位数符合条件并且 $ zerocount \; mod \,2\, =0 $ ，就得到一种解。代码：

#include<bits/stdc++.h>
using namespace std;

int ans = 0, n;
void dfs(int dep, int zero_count){
    if(dep > n){//数位 > n就有可能是解
        if(zero_count%2 == 0){
            ans++;//得到一种，计数器++；
        }
    } else {
        for(int i = 0; i <= 9; i++){
            if(i == 0){
                dfs(dep + 1, zero_count+1);//是0就记录0的个数
            } else {
                dfs(dep + 1, zero_count);
            }
        }
    }
}
int main(){
    int t;
    cin >> t;
    for(int i = 1; i <= t; i++){//无脑输入
        cin >> n;
        dfs(1, 0);
        cout << ans << endl;
        ans = 0;
    }
    return 0;
}