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

#define el '\n'
#define mxn 100005

struct node{
    int val;
    node *l, *r;
    node(int x){
        val = x;
        l = r = 0;
    }
};

void make(node *x, int v, char c){
    if(c == 'L') x->l = new node(v);
    else x->r = new node(v);
}

void insert(node *x, int u, int v, char c){
    if(!x) return;
    if(x->val == u){
        make(x, v, c); return;
    }
    insert(x->l, u, v, c);
    insert(x->r, u, v, c);
}

bool nto(int n){
    for(int i=2; i*i<=n; i++) if(n % i == 0) return 0;
    return n > 1;
}

int res;
void duyet(node *root, int cnt){
    if(root == nullptr) return;
    bool x = nto(root->val);
    cnt += x;
    res = max(res, cnt);
    duyet(root->l, cnt);
    duyet(root->r, cnt);
    cnt -= x;
}

void solve(){
    int n; cin >> n;
    node *root = nullptr;
    for(int i=0; i<n; i++){
        int u, v; char c;
        cin >> u >> v >> c;
        if(!i){
            root = new node(u);
            make(root, v, c);
        }else insert(root, u, v, c);
    }
    res = 0;
    duyet(root, 0);
    cout << res << el;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();

    cerr << "Execution Time: " << 0.001 * clock() << "s\n";
}

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

#define el '\n'
#define mxn 100005

struct node{
    int v;
    node *l, *r;
    node(int x){
        v = x;
        l = r = nullptr;
    }
};

int n, q, a[mxn];
vector<int> v;

void insert(node *&root, int x){
    if(root == nullptr){
        root = new node(x);
        return;
    }
    if(x < root->v) insert(root->l, x);
    else insert(root->r, x);
}

void inOrder(node *root){
    if(root == nullptr) return;
    inOrder(root->l);
    v.push_back(root->v);
    inOrder(root->r);
}

void solve(){
    cin >> n >> q;
    node *root = nullptr;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        insert(root, a[i]);
    }
    inOrder(root);
    while(q--){
        int x; cin >> x;
        int pos = lower_bound(v.begin(), v.end(), x) - v.begin();
        if(pos == v.size()){
            cout << v[pos - 1] << ' ' << "0\n";
        }else if(v[pos] == x){
            if(pos == 0) cout << "0 ";
            else cout << v[pos - 1] << ' ';
            if(pos == v.size() - 1) cout << "0\n";
            else cout << v[pos + 1] << el;
        }else{
            if(pos == 0) cout << "0 ";
            else cout << v[pos - 1] << ' ';
            cout << v[pos] << el;
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 100005

int n, a[mxn];
struct node{
    int val;
    node *l, *r;
    node(int x){
        val = x;
        l = r = 0;
    }
};
 
node* f[mxn * 4];
 
void inOrder(node *root){
    if(!root) return;
    inOrder(root->l);
    cout << root->val << ' ';
    inOrder(root->r);
}
 
void solve(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    f[1] = new node(a[1]);
    for(int i=2; i<=n; i++){
        if(i % 2 == 0){
            f[i] = new node(a[i]);
            f[i / 2]->l = f[i];
        }else{
            f[i] = new node(a[i]);
            f[(i - 1) / 2]->r = f[i];
        }
    }
    inOrder(f[1]);
    cout << el;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'

struct node{
    int val;
    node *l, *r;
    node(int x){
        val = x;
        l = r = 0;
    }
};
 
void ins(node *&x, int v){
    if(!x){
        x = new node(v);
        return;
    }
    if(v < x->val) ins(x->l, v);
    else ins(x->r, v);
}
 
void in(node *x){
    if(!x) return;
    in(x->l);
    in(x->r);
    cout << x->val << ' ';
}
 
int cnt = 1;
void solve(){
    cout << "Test #" << cnt++ << ": ";
    int n; cin >> n;
    int a[n+5];
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    node *x = nullptr;
    for(int i=1; i<=n; i++) ins(x, a[i]);
    in(x); cout << el;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'

struct node{
    string val;
    node *l, *r;
    node(string x){
        val = x;
        l = r = 0;
    }
};
 
void duyet(node *x){
    if(!x or x->val == "N") return;
    duyet(x->r);
    cout << x->val << ' ';
    duyet(x->l);
}
 
void solve(){
    string a; getline(cin >> ws, a);
    vector<string> v;
    stringstream ss(a);
    string tmp;
    while(ss >> tmp) v.push_back(tmp);
    queue<node*> q;
    node *root = new node(v[0]);
    q.push(root);
    int i = 1;
    while(!q.empty()){
        node *x = q.front(); q.pop();
        if(i == v.size()) break;
        x->l = new node(v[i]);
        if(v[i] != "N") q.push(x->l);
        ++i;
        if(i == v.size()) break;
        x->r = new node(v[i]);
        if(v[i] != "N") q.push(x->r);
        ++i;
    }
    duyet(root);
    cout << el;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'

struct node{
    int val;
    node *l, *r;
    node(int x){
        val = x;
        l = r = 0;
    }
};
 
node *ins(node *root, int x){
    if(!root) return new node(x);
    if(x < root->val) root->l = ins(root->l, x);
    else root->r = ins(root->r, x);
    return root;
}
 
node *find(node *root){
    while(root->l) root = root->l;
    return root;
}
 
node *del(node *root, int x){
    // nếu node cần xoá có giá trị nhỏ hơn giá trị node hiện tại
    // suy ra node cần xoá thuộc cây con bên trái của node hiện tại
    if(x < root->val) root->l = del(root->l, x);
    // tương tự với cây con bên phải
    else if(x > root->val) root->r = del(root->r, x);
    // đã tìm thấy node cần xoá
    else{
        // nếu node cần xoá không có cây con bên trái
        // thì ta chỉ cần "nối tiếp" cây con bên phải lên trên
        if(!root->l){
            node *tmp = root->r;
            delete root;
            return tmp;
        }
        // tương tự với cây con bên trái
        if(!root->r){
            node *tmp = root->l;
            delete root;
            return tmp;
        }
        // trường hợp có cả cây con bên trái và phải
        // ta sẽ chọn 1 trong 2 cách đều được
        // 1. tìm node nhỏ nhất của cây con bên phải
        // 2. tìm node lớn nhất của cây con bên trái
        // đây là phương án 1
        node *tmp = find(root->r);
        root->val = tmp->val;
        // sau khi cho node cần tìm thay thế lên node hiện tại
        // thì ta cần xoá bỏ cái node "cần tìm" đó
        root->r = del(root->r, tmp->val);
    }return root;
}
 
void pre(node *root){
    if(!root) return;
    cout << root->val << ' ';
    pre(root->l);
    pre(root->r);
}
 
void solve(){
    int q; cin >> q;
    node *root = nullptr;
    for(int i=1; i<=q; i++){
        cout << "Query #" << i << ": ";
        string s; cin >> s;
        int x; cin >> x;
        if(s == "ins") root = ins(root, x);
        else root = del(root, x);
        pre(root); cout << el;
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}