#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

// Uncomment line with "#define DEBUG" if you want to see your hashtable.
// But rememeber to send only solutions with debug turned off!
// #define DEBUG 1

#define MAX_CHARS 31
typedef unsigned int uint;

typedef enum states {
	EMPTY = 0,
	OCCUPIED = 1,
	STH_WAS_HERE = 2
} states;

typedef struct Slot {
	char name[MAX_CHARS];
	char phone[MAX_CHARS];
	states state;
} Slot;

uint hashfunc(const char* name) {
    /*char* result = (char*)malloc(sizeof(char*)*4);
    int i = 0;
    int hash = 0;
    for(i = 0; i < 4; i++) result[i] = '0';
    for(i = 0; i < 4 && name[i] != '\0'; i++) result[i%4] = result[i%4] ^ name[i];
    for(i = 0; i < 4; i++)
    {
        hash += result[i];
        if(i != 3) hash = hash << 8;
    }
    free(result);
    return hash; */
    int p = 2137;
    uint h = 0;
    int i = 0;
    for(i = 0; i < strlen(name); i++){
        if(name[i] == '\0') break;
        h = h*p +name[i];
    }
    return h;
    /**********************
    * PLACE FOR YOUR CODE *
    **********************/
}

void add_to_hashtable(Slot** hashtable, int n, const char* name, const char* phone) {
    if(n == 0) return;
	uint hash = hashfunc(name) % n;
    /**********************
    * PLACE FOR YOUR CODE *
    **********************/
    // find a good spot for placing this entry!
    // You may use this:
    //uint hash = ???;
    while (hashtable[hash]->state == OCCUPIED) {
         hash = (hash+1)%n;
    }
	hashtable[hash]->state = OCCUPIED;
	strcpy(hashtable[hash]->name, name);
	strcpy(hashtable[hash]->phone, phone);
}

char* get_number(Slot** hashtable, int n, const char* name) {
	if (n == 0) return NULL;
	uint hash = hashfunc(name) % n;
    while(hashtable[hash]->state == STH_WAS_HERE || (hashtable[hash]->state == OCCUPIED && strcmp(hashtable[hash] -> name, name) != 0)) hash = (hash+1)%n;
    if(hashtable[hash] -> state == EMPTY) return NULL;
    return hashtable[hash] -> phone;
    /**********************
    * PLACE FOR YOUR CODE *
    **********************/
}

void remove_from_hashtable(Slot** hashtable, int n, const char* name) {
    if(n == 0) return;
	uint hash = hashfunc(name) % n;
    while((hashtable[hash]->state == OCCUPIED && strcmp(hashtable[hash] -> name, name) != 0) || hashtable[hash]->state == STH_WAS_HERE) hash = (hash+1)%n;
    if(hashtable[hash] -> state == EMPTY) return;
    /**********************
    * PLACE FOR YOUR CODE *
    **********************/
    //hashtable[hash]->name[0] = "\0";
	hashtable[hash]->state = STH_WAS_HERE;
}


void free_memory(Slot** hashtable, int n) {
	for (int i = 0; i < n; i++) {
		free(hashtable[i]);
	}
	free(hashtable);
}

void debug_print_hashtable(Slot** hashtable, int n) {
	#ifdef DEBUG
		for (int i = 0; i < n; i++) {
			printf("%d: [%d] %s\n", hashtable[i]->state, hashtable[i]->name);
		}
		printf("\n");
	#endif
}

int main() {
    int Z;
    scanf("%d", &Z);
	while (Z--) {
		int n, k;
		char op;
		char tmp_name[MAX_CHARS], tmp_phone[MAX_CHARS];

        scanf("%d", &n);
        scanf("%d", &k);
		int size = n * 10;

		Slot** hashtable = (Slot**)calloc(size, sizeof(Slot*));

		for (int i = 0; i < size; i++) {
			hashtable[i] = (Slot*) malloc(sizeof(Slot));
			hashtable[i]->state = EMPTY;
		}

		for (int i = 0; i < k; i++) {
			do { scanf("%c", &op); } while(isspace(op));
			switch(op) {
				case 'a':
                    scanf("%s", tmp_name);
                    scanf("%s", tmp_phone);
					add_to_hashtable(hashtable, size, tmp_name, tmp_phone);
					break;
				case 'r':
                    scanf("%s", tmp_name);
					remove_from_hashtable(hashtable, size, tmp_name);
					break;
				case 'g':
                    scanf("%s", tmp_name);
					char* num = get_number(hashtable, size, tmp_name);
					printf("%s\n", num ? num : "");
					break;
			}
			debug_print_hashtable(hashtable, size);
		}
		free_memory(hashtable, size);
	}
	return 0;
}