#include<iostream>
#include<queue>
#include<stack>

using namespace std;

int main(){

    int m, n, num;
    char str1[15], str2[15];

    cin >> n;
    while (n--){
        scanf("%d %s", &m, str1);
        if (str1[2] == ‘F‘){
            queue<int>q;
            while (m--){
                scanf("%s", str2);
                if (str2[0] == ‘I‘){
                    cin >> num;
                    q.push(num);
                }
                else{
                    if (q.empty()){
                        cout << "None"<<endl;
                    }
                    else{
                        cout << q.front() << endl;
                        q.pop();
                    }
                }

            }
        }
        if (str1[2] == ‘L‘){
            stack<int>s;
            while(m--){
                scanf("%s", str2);
                if (str2[0] == ‘I‘){
                    cin >> num;
                    s.push(num);
                }
                else{
                    if (s.empty()){
                        cout << "None" << endl;
                    }
                    else{
                        cout << s.top() << endl;
                        s.pop();
                    }
                }
            }
        }
    }


    system("pause");
    return 0;
}