Description

你的任务是实现这样一个队列。一开始，队列里的元素被初始化为 1, 2, 3, ... n 。我们对他有这样两种操作：

Top x ：将 x 提到队首（1 <= x <= n）；

Next：输出队首元素，并将队首元素放到队尾。

Input

第一行为一个整数 T ，表示有 T 组测试数据。 每组数据的第一行有两个整数 n 和 m (n, m <= 1000) 。接下来 m 行操作序列，每行包含一个操作。

Output

对于每个 Next ，输出一个答案。

Sample

Input

2
10 5
Top 4
Next
Top 5
Next
Next
8 6
Next
Next
Top 7
Next
Top 4
Next

Output

4
5
1
1
2
7
4

Source: ycc