SubsetMex

Ένα multiset είναι μια συλλογή στοιχείων παρόμοια με το set, όπου τα στοιχεία μπορούν να επαναλαμβάνονται. Για παράδειγμα, το επόμενο είναι ένα multiset:

{~0, 0, 1, 2, 2, 5, 5, 5, 8~}

Δίνεται multiset ~S~ που περιέχει μη αρνητικούς ακεραίους και μια μη αρνητική ακέραια τιμή στόχο, τη ~n~, τέτοια ώστε η ~n~ δεν περιέχεται στο ~S~ και το ζητούμενο είναι να εισάγετε την τιμή ~n~ στο ~S~ ακολουθώντας μια διαδικασία ~3~ βημάτων, επαναλαμβανόμενα:

1. Επιλέξτε ένα (πιθανόν άδειο) υποσύνολο ~T~ του ~S~. Έστω, ~T~ ένα σύνολο από διακριτούς αριθμούς που εμφανίζονται στο ~S~.

2. Διαγράψτε τα στοιχεία του ~T~ από το ~S~. (Αφαιρέστε μόνο ένα αντίγραφο από κάθε στοιχείο.)

3. Εισάγετε το mex~(T)~ στο ~S~, όπου mex~(T)~ είναι ο μικρότερος μη αρνητικός ακέραιος που δεν περιέχεται στο ~T~. Ο μαθηματικός όρος mex είναι συντομογραφία για την "minimum excluded" τιμή.

Ο στόχος σας είναι να βρείτε τον μικρότερο αριθμό διαδικασιών ώστε ο ~n~ να γίνει μέλος του ~S~.

Καθότι το μέγεθος του ~S~ μπορεί να είναι μεγάλο, θα δίνεται στη μορφή λίστας ~(f_0, \cdots, f_{n - 1})~ μεγέθους ~n~, όπου το ~f_i~ αναπαριστά τον αριθμό των εμφανίσεων του αριθμού ~i~ στο ~S~. (Σημειώστε ότι το ~n~ είναι ο αριθμός που προσπαθούμε να εισάγουμε στο ~S~.)

Είσοδος

Η πρώτη γραμμή περιέχει έναν και μόνο ακέραιο ~t (1 \le t \le 200)~ - τον αριθμό των δοκιμαστικών περιπτώσεων. Κάθε δύο επόμενες γραμμές, περιγράφουν μια δοκιμαστική περίπτωση:

• Η πρώτη γραμμή της κάθε δοκιμαστικής περίπτωσης περιέχει έναν μόνο ακέραιο ~n (1 \le n \le 50)~, που αναπαριστά τον αριθμό που θέλουμε να εισαχθεί στο ~S~.

• Η δεύτερη γραμμή της κάθε δοκιμαστικής περίπτωσης περιέχει ~n~ ακέραιους ~f_0, f_1, \cdots, f_{n - 1} (0 \le f_i \le 10^{16})~, που αναπαριστούν το multiset ~S~ όπως εξηγήθηκε παραπάνω.

Έξοδος

Για κάθε δοκιμαστική περίπτωση, τυπώστε σε μια γραμμή, τον αριθμό που αναπαριστά τον ελάχιστο αριθμό διεργασιών που απαιτούνται για να ικανοποιήσουν το στόχο σας.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~5~	~n \le 2~
~2~	~17~	~n \le 20~
~3~	~7~	~f_i = 0~
~4~	~9~	~f_i \le 1~
~5~	~20~	~f_i \le 2000~
~6~	~9~	~f_0 \le 10^{16}~ και ~f_i = 0~ (για κάθε ~j \ne 0~)
~7~	~10~	Υπάρχει μια τιμή ~i~ για την οποία ~f_i \le 10^{16}~ και ~f_j = 0~ (για κάθε ~j \ne i~))
~8~	~23~	Κανένας επιπλέον περιορισμός.

Παράδειγμα

input

2
4
0 3 0 3
5
4 1 0 2 0

output

4
10

Σημείωση: Στο παράδειγμα, αρχικά ~S~ ~=~ {~1, 1, 1, 3, 3, 3~} και ο στόχος σας είναι να εισαχθεί το ~4~ στο ~S~. Μπορείτε να κάνετε τα ακόλουθα:

1. επιλέξτε ~T~ ~=~ {}, οπότε το ~S~ γίνεται {~0, 1, 1, 1, 3, 3, 3~}

2. επιλέξτε ~T~ ~=~ {~0, 1, 3~}, οπότε το ~S~ γίνεται {~1, 1, 2, 3, 3~}

3. επιλέξτε ~T~ ~=~ {~1~}, οπότε το ~S~ γίνεται {~0, 1, 2, 3, 3~}

4. επιλέξτε ~T~ ~=~ {~0, 1, 2, 3~}, οπότε το ~S~ γίνεται {~3, 4~}