#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <map>
using namespace std;

int n;

int main()
{
	scanf("%d",&n);
	stack<int> a[10];
	queue<int> b[10];
	while(n--){
		int m;
		char str[10];
		scanf("%d %s",&m,str);
		char str1[10];
		int m1;
		if(str[2]==‘F‘){
			queue<int> q;				//定义队列q 
			while(m--){
				scanf("%s",str1);
				if(str1[0]==‘I‘){
					scanf("%d",&m1);
					q.push(m1);
				}
				else{
					if(q.empty()){
						printf("None\n");
					}
					else{
						printf("%d\n",q.front());		//取队首元素 
						q.pop();
					}
				}
			}
		} 
		if(str[2]==‘L‘){
			stack<int> s;					//定义堆栈s 
			while(m--){
				scanf("%s",str1);
				if(str1[0]==‘I‘){
					scanf("%d",&m1);
					s.push(m1);
				}
				else{
					if(s.empty()){
						printf("None\n");
					}
					else{
						printf("%d\n",s.top());			//取栈顶元素 
						s.pop();
					}
				}
			}
		}
	}
	return 0;
}