Chintamani is throwing a party tonight (YAY!!! :)) But there is a slight problem. He ordered a packet of toffees. Fussy he is, he had given strict orders to the shopkeeper that in the packet all toffees should be of different kind. That is no more than one toffee of each variety should be there.

Each type of toffee has a unique identification number written on it. He has received the packet from the shopkeeper but he wants to check the same. He starts taking out toffee from the packet one by one saying the id number of the toffee.

Help him in this task by telling him whether a toffee with the id number he just said has occurred before or not.

Input

The first line of the input will be the number of test cases (T <= 10). For each test case first line contains one integer n denoting the number of toffees in the packet 0 <= n <= 10^6. n lines follow each containing the id number for a toffee. 0 <= id <= 10^9.

Output

You have to output total n lines for each test case. For each input if the toffee with the given id has already occurred output "DUPLICATE" else output "OK".

Example

Input:
2
4
7
5
1
5
3
2
2
1

Output:
OK
OK
OK
DUPLICATE
OK
DUPLICATE
OK