“Never forget what you are, the rest of the world will not. Wear it like armor and it can never be used to hurt you.” -Tyrion Lannistar
Tyrion realizes that he has come to a complete new world after watching "Drogo" - the black dragon. To solve the problem about Drogo eating animals and children, Tyrion discovered a magical Stack.
Tyrion's servants place wild animals or sheep on the magical Stack. Drogo can eat only the animal placed on the top of the stack. Moreover, the animal placed on the top of the magical Stack can be replicated again after removal by Drogo by some magic.
Eg: Suppose the magical Stack has animals 1 1 2 3 4 5 (Bottom to Top). Drogo can eat animals in many sequences and some of them are
5 5 5 5 4 3 3 2 2 1 1 1
5 4 4 3 3 2 1 1
Now Missandei - maid of Daenerys has decided a menu for Drogo in terms of a sequence of N animals and the sequence should be strictly followed. Now Tyrion is wondering - How many minimum number of animal will be required to be pushed on the stack (not counting the replicated ones).
Input Format
First Line contains T the number of test cases.
Second line contains an integers N indicating the number of animals Drogo has to eat.
Next line contains N space separated integers indicating the animal number Drogo has to eat.
Output Format
One line containing an integer denoting the answer as specified above.
Constrains
1 <= T <= 10
1 <= N <= 100
1 <= Each animal number <= 1000
1. Push 1 into stack and print top [Current Stack : 1]
2. Push 2 into stack and print top [Current Stack : 1 2]
3. Push 1 into stack, print top twice and pop it from stack [Current Stack : 1 2]
4. Push 3 into stack, print top and pop it from stack [Current Stack : 1 2]
5. Print top & pop 2 from stack [Current Stack : 1]
6. Print top [Current Stack : 1]
So total animals pushed on the stack are 4 and others are replicated and thus the magic works!!
