#include<iostream>//完全模拟队列和栈
#include<string>
using namespace std;
const int MAX = 100005;
struct stack
{
int top;
int a[MAX];
}s;
struct queue
{
int top;
int base;
int a[MAX];
}ss;
void push(int a)
{
s.a[s.top++] = a;
}
void push1(int a)
{
ss.a[ss.top++] = a;
}
//void top()
int main()
{
int t, n, m, i;
char str[5];
char str1[5];
cin>>t;
while(t--)
{
cin>>n>>str1;
ss.top = 0;
ss.base = 0;
s.top = 0;
if(strcmp(str1, "FIFO") == 0)
{
for(i = 0; i < n; i++)
{
cin>>str;
if(strcmp(str,"IN") == 0)
{
cin>>m;
push1(m);
}
else
{
if(ss.top == ss.base)
cout<<"None"<<endl;
else
{
cout<<ss.a[ss.base]<<endl;
ss.base++;
}
}
}
}
else
{
for(i = 0 ; i < n ; i++)
{
cin>>str;
if(strcmp(str,"IN") == 0)
{
cin>>m;
push(m);
}
else
{
if(s.top == 0)
cout<<"None"<<endl;
else
{
cout<<s.a[s.top - 1]<<endl;
s.top--;
}
}
}
}
}
}