Mr. K. I. has a very big movie collection. He has organized his collection in a big stack. Whenever he wants to watch one of the movies, he locates the movie in this stack and removes it carefully, ensuring that the stack doesn’t fall over. After he ﬁnishes watching the movie, he places it at the top of the stack.
Since the stack of movies is so big, he needs to keep track of the position of each movie. It is sufﬁcient to know for each movie how many movies are placed above it, since, with this information, its position in the stack can be calculated. Each movie is identiﬁed by a number printed on the movie box.
Your task is to implement a program which will keep track of the position of each movie. In particular, each time Mr. K. I. removes a movie box from the stack, your program should print the number of movies that were placed above it before it was removed.
On the ﬁrst line a positive integer: the number of test cases, at most 100. After that per test case:
For simplicity, assume the initial stack contains the movies with identiﬁcation numbers 1, 2, ..., n in increasing order, where the movie box with label 1 is the top-most box.
Per test case:
Note that after each locate request ai, the movie box with label ai is placed at the top of the stack.
2 3 3 3 1 1 5 3 4 4 5
2 1 0 3 0 4