//用樹狀數(shù)組實現(xiàn)求和和查詢第k個元素的功能
#include <stdio.h>
#include <memory>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <cmath>
#include <set>
#include <queue>
#include <time.h>
#include <limits>
using namespace std;
#define N 100005
#define typev int
typev ar[N*2];
int ks[N], num[N], pos[N], id[N];
bool has[N];
int kn, n, qn, fr;
char qs[N];
int vMax;
int lowb(int t){ return t & (-t); }
void add(int i, typev v){
for(; i < vMax; ar[i] += v, i += lowb(i)) ;
}
typev sum(int i){
typev s = 0;
for(; i > 0; s += ar[i], i -= lowb(i));
return s;
}
int find_k(int k){ //find the kth number
int pos = 0, cnt = 0, i;
for(i = log((double)vMax) / log(2.0) + 1; i >= 0; i--){
pos += (1 << i);
if(pos >= vMax || cnt + ar[pos] >= k) pos -= (1 << i);
else cnt += ar[pos];
}
return pos + 1;
}
bool input(){
scanf("%d%d", &n, &qn);
int i;
char ops[10];
for(i = 0; i < qn; i++){
scanf("%s%d", ops, num+i);
ks[i] = num[i];
qs[i] = ops[0];
}
return true;
}
void init(){
kn = qn;
ks[kn++] = 1;
sort(ks, ks+kn);
int i, j;
j = 1;
for(i = 1; i < kn; i++){
if(ks[i] != ks[j-1]) ks[j++] = ks[i];
}
kn = j;
vMax = qn + kn + 1;
fill(ar, ar+vMax+1, 0);
fr = qn;
}
int cnt = 0;
void solve(){
int i, pMax, val, p, s, ans;
init();
ks[kn] = n+1;
for(i = 0; i < kn; i++){
has[i] = true;
val = ks[i+1]-ks[i];
pos[i] = qn + i + 1;
add(pos[i], val);
}
printf("Case %d:\n", ++cnt);
for(i = 0; i < qn; i++){
if(qs[i] == 'T'){
p = lower_bound(ks, ks+kn, num[i]) - ks;
has[p] = false;
val = -1;
add(pos[p], val);
val = 1;
id[fr] = num[i];
pos[p] = fr--;
add(pos[p], val);
}else if(qs[i] == 'R'){
p = find_k(num[i]);
if(p <= qn){
ans = id[p];
}else{
s = sum(p-1);
ans = num[i] - s + ks[p - qn - 1] - 1;
if(!has[p - qn - 1]) ans++;
}
printf("%d\n", ans);
}else{ //'Q'
p = lower_bound(ks, ks+kn, num[i]) - ks;
ans = sum(pos[p] - 1);
printf("%d\n", ans + 1);
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while(t--){
input();
solve();
}
return 0;
}