Organize The Wallet

All submissions for this problem are available.
Ranju has many currency notes in his wallet. There are notes of denominations 10, 20, 50, 100, 200, 500, and 2000 rupees in his wallet right now, but the notes are all messed up. He wants to organize his wallet so that all the notes of each denomination are together. The notes don't necessarily need to be in sorted order.
In each step, Ranju can take a note and insert this note at any place among the remaining notes. Please determine the minimum number of steps he requires to achieve his goal.
Input
The first line of the input is the number of test cases, T. Description of each test case is given below.
The first line of each testcase contains a single integer, N, the number of notes in the wallet.
The next line contains N integers: A_{1}, A_{2}, A_{3}, ... , A_{N} which represent the notes in the wallet at the initial state.
Output
For each test case, print the minimum number of steps required to organize the wallet, in a new line.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N ≤ 10^{5}
 Each of A_{i} will be from the set {10, 20, 50, 100, 200, 500, 2000}
Example
Input: 2 6 500 500 100 200 200 100 9 100 200 200 500 100 100 500 100 100 Output: 1 2
Explanation
Testcase 1: We can move the last 100 rupee note and insert it to the right of 1^{st} 100 rupee note. The result would be 500 500 100 100 200 200.
Testcase 2: One possible way would be the following:
 In the first step, we can move the first note, which has denomination 100 next to 7th note, which has denomination 500. The result will be : 200 200 500 100 100 500 100 100 100.
 In the second step, we can move the 6th note, which has denomination 500 to the right of the 3rd note, which has denomination 500. The result will be 200 200 500 500 100 100 100 100 100
Author:  zubaerkh 
Tags  dp+bitmask, gwr17rol, mediumhard, zubaerkh 
Date Added:  8112017 
Time Limit:  7 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 