Due to their love for ice cream and having almost nothing to do after placements, Aditi and co. have opened up a ice cream parlour in KNGH itself. Research shows that if a customer arrives and there are no empty seats available , the customer will turn around and leave, thus costing the group. Your task is to write a program that tells the group how many customers left without a ice cream.
Input : First line of input contains T, the number of test cases.
First line of each test case contains a positive integer N, representing the number of seats in the parlour. Second line of each test case contains a sequence of uppercase letters. Letters in the sequence occur in pairs. The first occurrence indicates the arrival of a customer, the second indicates the departure of that same customer. No letter will occur in more than one pair. Customers who leave without a ice cream always depart before customers who are currently sitting and eating a icecream. You may assume that only one person can sit in one seat. There are at most 20 seats per parlour.
Output : For each test case, output a sentence telling how many customers, if any, walked away. Use the exact format shown below in sample outputs.
Constraints : 1 <= T <= 1000 0 <= N <= 20 2 <= Length of customer string <= 52 Length of customer string is always even