// Arup Guha
// 2/26/2024
// Solution to COP 4516 Final Individual Contest Problem: The Grand Social Gathering

import java.util.*;

public class social {

	public static void main(String[] args) {
	
		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();
		
		// Process cases.
		for (int loop=0; loop<nC; loop++) {

			// We store lots of stuff.
			int n = stdin.nextInt();
			
			// This map stores for each name how many times it appears.
			TreeMap<String,Integer> nameMap = new TreeMap<String,Integer>();
			
			// Process queries.
			for (int i=0; i<n; i++) {
				
				String cmd = stdin.next();
				
				// Adding a name.
				if (cmd.equals("ADD")) {
					String name = stdin.next();
					
					// New name, so we're add to map.
					if (!nameMap.containsKey(name)) 
						nameMap.put(name, 0);
					
					// Update count.
					nameMap.put(name, nameMap.get(name)+1);
				}
				
				// A query.
				else if (cmd.equals("QUERY")) {
					
					// This portion is easy - the map stores it.
					String name = stdin.next();
					System.out.print(nameMap.get(name));
					
					// Get next name and print.
					String next = nameMap.higherKey(name);
					String res = next == null ? "None" : next;
					System.out.println(" "+res);
				}
				
				// Remove case.
				else {
					
					// Remove from frequency f.
					String name = stdin.next();
					int freq = nameMap.get(name);
					
					// Just need to remove this name from the whole name map.
					if (freq == 1) 
						nameMap.remove(name);
					
					// Need to update the frequency here.
					else 
						nameMap.put(name, freq-1);
				}
			}
		}
	}
}