#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
class node;
node * Tree_root;
class node
{
public:
    node * left;
    node * parent;
    node * right;
    char name[15];
    long long value;

    node(long long V, char N[], node * P){
        left = NULL;
        right= NULL;
        parent = P;
        strcpy(name, N);
        value = V;
    };
    ~node(){
        if(left) delete left;
        if(right) delete right;
    };

    static bool insert(node * root, node * to_add){

        if(root->value==to_add->value)
            return false;

        if(root->value > to_add->value){
            if(root->left==NULL){
                root->left = to_add;
                to_add->parent = root;
            } else {
                return insert(root->left, to_add);
            }
        } else {
            if(root->right==NULL){
                root->right = to_add;
                to_add->parent = root;
            } else {
                return insert(root->right, to_add);
            }
        }
        return true;
    };
    static node *find(node * root, long long  V){ //znajduje element o wartosci V
        if(root==NULL){
            return NULL;
        } else {
            if(root->value==V){
                return root;
            } else if(root->value>V) {
                return find(root->left, V);
            } else{
                return find(root->right, V);
            }
        }
    };
    static void remove(long long V){
    };
    static bool del(node * &root, long long  V){ //usuwa element o kluczu V
        node *DelNode = find(root, V);
        if(DelNode==NULL){
            return false;
        }
        if(DelNode->left==NULL && DelNode->right==NULL){ //brak synow
            if(DelNode==Tree_root){
                Tree_root = NULL;
                //return true;
            } else {
                if(DelNode==DelNode->parent->left){ //usuwany jest lewy
                    DelNode->parent->left = NULL;
                    //return true;
                }else if(DelNode==DelNode->parent->right){ //usuwany jest prawy
                    DelNode->parent->right = NULL;
                    //return true;
                }
            }
        } else if(DelNode->left!=NULL && DelNode->right==NULL){ //tylko lewy syn
            if(DelNode==Tree_root){ //jak usuwany jest korzeniem
                Tree_root = Tree_root->left;
                Tree_root->parent=NULL;
                //return true;
            } else {
                if(DelNode==DelNode->parent->left){ //usuwany jest lewy
                    DelNode->parent->left = DelNode->left;
                    DelNode->left->parent = DelNode->parent;
                    //return true;
                } else
                if(DelNode==DelNode->parent->right){ //usuwany jest prawy
                    DelNode->parent->right = DelNode->left;
                    DelNode->left->parent = DelNode->parent;
                    //return true;
                }
            }
        } else if(DelNode->left==NULL && DelNode->right!=NULL){ //tylko prawy syn
            if(DelNode==Tree_root){ //jak usuwany jest korzeniem
                Tree_root = Tree_root->right;
                Tree_root->parent=NULL;
                //return true;
            } else {
                if(DelNode==DelNode->parent->left){ //usuwany jest lewy
                    DelNode->parent->left = DelNode->right;
                    DelNode->right->parent = DelNode->parent;
                    //return true;
                } else
                if(DelNode==DelNode->parent->right){ //usuwany jest prawy
                    DelNode->parent->right = DelNode->right;
                    DelNode->right->parent = DelNode->parent;
                    //return true;
                }
            }
        } else if(DelNode->left!=NULL && DelNode->right!=NULL){ //lewy i prawy syn
            node * next = succ(DelNode);
            strcpy(DelNode->name,  next->name);
            DelNode->value = next->value;
            //zastąpienie następnika jego prawym synem
            node * par = next->parent;
            if(next->right==NULL){
                if(next==par->right){
                    par->right = NULL;
                } else if(next==par->left){
                    par->left = NULL;
                }
            } else{
                if(next==par->right){
                    par->right = next->right;
                    next->right->parent = par;
                } else if(next==par->left){
                    par->left = next->right;
                    next->right->parent = par;
                }
            }
            //return true;
        }

        return true;
    };
    static void print(node * root){
        if(root -> left != NULL){
            print(root -> left);
        }
        printf("%010lld ", root->value);
        //cout << "Main: " << root <<" parent: " << root->parent << " left: " << root->left <<" right:" << root->right << endl;
        //cout << root->name << endl;
        printf("%s\n", root->name);
        if(root ->right != NULL){
            print(root ->right);
        }
    };
    static bool cmp(string &a, string &b){
        return false;
    };
    static node * succ(node * x)
    {
        if(x->right) return minnode(x->right);

        node * y;

        do
        {
            y = x;
            x = x->parent;
        } while(x && (x->left != y));

        return x;
    }
    static node * minnode(node * x){
        if(x!=NULL){
            while(x->left!=NULL)
                x = x->left;
        }
        return x;
    }
};

int main(){
    int z;
    scanf("%d", &z);
    while(z--){
        int n;
        Tree_root = NULL;
        scanf("%d", &n);
        for(int i = 0; i<n; i++){
            char cmd[20];
            scanf("%s", cmd);
            if(cmd[0]=='I'){
                long long V;
                char name[15];
                scanf("%lld%s", &V, name);
                node * temp = new node(V, name, NULL);
                if(Tree_root==NULL){
                    Tree_root = temp;
                    printf("OK\n");
                } else{
                    if(node::insert(Tree_root, temp)){
                        printf("OK\n");
                    } else {
                        delete temp;
                        printf("ERROR\n");
                    }
                }
            } else if(cmd[0]=='F'){
                long long V;
                scanf("%lld", &V);
                node * res = node::find(Tree_root, V);
                if(res == NULL){
                    printf("FIND ERROR\n");
                } else {
                    printf("FIND %010lld %s\n", res->value, res->name);
                }
            } else if(cmd[0]=='D'){
                long long V;
                scanf("%lld", &V);
                bool res = node::del(Tree_root, V);

                if(res==false){
                    printf("ERROR\n");
                } else{
                    //res->left = NULL;
                    //res->right = NULL;
                    //delete res;
                    printf("OK\n");
                }
                //delete res;
            } else if(cmd[0]=='P'){
                if(Tree_root==NULL){
                    printf("EMPTY\n");
                } else{
                    node::print(Tree_root);
                }
            }
        }
        delete Tree_root;
    }
    return 0;
}