#include<bits/stdc++.h>
using namespace std;
void solve(){
	int n;
	string s;
	cin>>n>>s;
	int cnt1,cnt0;
	cnt1=cnt0=0;
	for(auto c:s){
		if(c=='0'){
			cnt0++;
		}else{
			cnt1++;
		}
	}
	int p=1;
	while(cnt1 && cnt0){
		if(p%2){
			cnt1--;
		}else{
			cnt0--;
		}
		p++;
	}
	if(p%2){
		cout<<"Tai"<<endl;
	}else{
		cout<<"Wei"<<endl;
	}
}
int main(){
	int n;
	cin>>n;
	while(n--){
		solve();
	}
	return 0; 
}

#include<bits/stdc++.h>
using namespace std;
string s;
int n;
vector<string>ans;
string ys[]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
void dfs(int u,string str){
	if(u==n+1){
		ans.push_back(str);
		return ;
	}
	int aj=s[u]-'0';
	for(auto c:ys[aj]){
		dfs(u+1,str+c);
	}
}
int main(){
	cin>>s;
	n=s.size();
	s=" "+s;
	dfs(1,"");
	cout<<ans.size()<<endl;
	for(auto str:ans) cout<<str<<" ";
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int num, n, m;
char g[N][N];
bool check(int x, int y, int direction) {
    int step = num;
    while (g[x][y] != 'O') {
        int nx = x + dx[direction], ny = y + dy[direction];
        if (nx < 1 || nx > n || ny < 1 || ny > m) {
            return false;
        }
        if (step == 0) {
            return false;
        }
        if (g[nx][ny] == 'E') {
            direction = (direction + 1) % 4;
        } else if (g[nx][ny] == 'W') {
            direction = (direction + 3) % 4;
        }
        step--;
        x = nx, y = ny;
    }
    return true;
}
int main() {
    cin >> num >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }
    struct node {
        int x, y;
    };
    vector<node> res;
    for (int i = 2; i <= m - 1; i++) {
        if (g[1][i] == '.' && check(1, i, 1)) {
            res.push_back({1, i});
        }
        if (g[n][i] == '.' && check(n, i, 3)) {
            res.push_back({n, i});
        }
    }
    for (int i = 2; i <= n - 1; i++) {
        if (g[i][1] == '.' && check(i, 1, 0)) {
            res.push_back({i, 1});
        }
        if (g[i][m] == '.' && check(i, m, 2)) {
            res.push_back({i, m});
        }
    }
    if (res.size() == 0) {
        cout << "not exist\n";
    } else {
        cout << res.size() << '\n';
        for (auto x : res) {
            cout << x.x - 1 << ' ' << x.y - 1 << '\n';
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5,mod=1e5+3;
vector<int>g[N];
int cnt[N], d[N];
bool vis[N];
void bfs(int s) {
	memset(d, 0x3f, sizeof d);
	       cnt[1] = 1;
	       queue<int>q;
	       q.push(1);
	       d[1] = 0;
	while (q.size()) {
	auto f = q.front();
		q.pop();
		for (auto node : g[f]) {
			if (d[f] + 1 < d[node]) {
				d[node] = d[f] + 1;
				q.push(node);
				cnt[node] = cnt[f];
			} else if (d[f] + 1 == d[node]) {
				cnt[node] +=cnt[f];
				cnt[node]%=mod;
			}
		}
	}
}
int main() {
	int n, m;
	cin >> n >> m;
	while (m--) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	bfs(1);
	for (int i = 1; i <= n; i++) {
		cout << cnt[i] << endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    long long a = 0, b = 0, c = 0, d = 0;
    for (char ch : s) {
        if (ch == 'A') {
            a++;
        } else if (ch == 'B') {
            b += a;
        } else if (ch == 'C') {
            c += b;
        } else if (ch == 'D') {
            d += c;
        }
    }
    cout << d;
    return 0;
}

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

bool canReach(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, 0});
    while (!q.empty()) {
        auto current = q.front();
        q.pop();
        int num = current.first;
        int steps = current.second;
        if (num == y) {
            return true;
        }
        if (steps >= 7) {
            continue;
        }
        int next1 = num / 2 + 7;
        q.push({next1, steps + 1});
        int next2 = num * 3 - 7;
        q.push({next2, steps + 1});
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int x, y;
        cin >> x >> y;
        if (canReach(x, y)) {
            cout << "cao_zhi!" << endl;
        } else {
            cout << "cao_pi!" << endl;
        }
    }
    return 0;
}

```cpp

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

long long countValidNumbers(long long N) {
    long long count = 0;
    queue<long long> q;
    q.push(1); // Start with 1, since numbers can't start with 0
    
    while (!q.empty()) {
        long long current = q.front();
        q.pop();
        if (current > N) {
            continue;
        }
        count++;
        q.push(current * 10);     // Append 0
        q.push(current * 10 + 1); // Append 1
    }
    return count;
}

int main() {
    long long N;
    cin >> N;
    cout << countValidNumbers(N) << endl;
    return 0;
}