#include<stdio.h>

#include<string.h>

#include<queue>

#include<stack>

#define N 10

using namespace std;

void Q(int n)

{

    int m;

    char s[N];

    queue<int>Q;

    while(n--)

    {

        scanf("%s", s);

        if(strcmp(s, "IN") == )

        {

            scanf("%d", &m);

            Q.push(m);

        }

        else if(strcmp(s, "OUT") == )

        {

            if(Q.empty())

                printf("None\n");

            else

            {

                printf("%d\n", Q.front());

                Q.pop();

            }

        }

    }

}

void S(int n)

{

    stack<int>S;

    char s[N];

    int m;

    while(n--)

    {

        scanf("%s", s);

        if(strcmp(s, "IN") == )

        {

            scanf("%d", &m);

            S.push(m);

        }

        else if(strcmp(s, "OUT") == )

        {

            if(S.empty())

            {

                printf("None\n");

            }

            else

            {

                printf("%d\n", S.top());

                S.pop();

            }

        }

    }

}

int main()

{

    int t, n;

    char s[N];

    scanf("%d", &t);

    while(t--)

    {

        scanf("%d%s", &n, s);

        if(strcmp(s, "FIFO") == )

            Q(n);

        else if(strcmp(s, "FILO") == )

            S(n);

    }

    return ;

}