Halloween
Limit pamięci: 128 MB
Niedługo Halloween! Bajtazar, świeżo upieczony student, nie wie za kogo się przebrać
ani gdzie iść balować podczas najbliższego święta. Najlepszą opcją pozostaje pójście na wiele imprez.
Na każdą imprezę chce założyć pewien strój. Przykładowo, u Bajtonerda chciałby
przebrać się za Informatyka Zombie, a u Bitokuli za Drakulę.
Bajtazar ma zamiar odwiedzić wiele imprez, na których chce być w różnych kostiumach.
Aby ułatwić sobie sprawę z przebieraniem, może on zakładać dowolnie wiele kostiumów.
Przykładowo, może nałożyć strój Drakuli na strój Kaczora Donalda, a pod
strojem Kaczora może mieć strój Predatora.
Przed każdą imprezą Bajtazar może zdjąć bądź założyć na siebie dowolną liczbę
kostiumów (oczywiście zdejmuje najbardziej wierzchnie i zakłada na ten najbardziej wierzchni).
Jeżeli Bajtazar ma na sobie nałożony kostium Frankensteina, a pod nim kostium King Konga
i idzie na imprezę, na której chce być przebrany za King Konga, to może albo zdjąć
kostium Frankensteina, albo założyć nowy kostium King Konga na kostium Frankensteina.
Bajtazar nie lubi się ubierać, więc chciałby jak najmniej razy zakładać na siebie kostium.
Mając podaną liczbę imprez, liczbę różnych kostiumów oraz ciąg numerów kostiumów, które obowiązują
na kolejnych imprezach, odpowiedz na pytanie: ile minimalnie razy Bajtazar musi zakładać
na siebie kostium.
Zakładamy, że Bajtazar ma dowolnie dużą liczbę kostiumów.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba (),
równa liczbie zestawów danych. Opis każdego zestawu danych składa się z dwóch wierszy.
Pierwszy z nich zawiera dwie liczby i (),
oznaczające liczbę różnych kostiumów (kostiumy są numerowane od 1 do ),
które obowiązują na imprezach, które ma zamiar odwiedzić Bajtazar oraz liczbę imprez.
Drugi wiersz zawiera ciąg liczb reprezentujących numery kostiumów, obowiązujących na kolejnych imprezach odwiedzanych przez Bajtazara.
Wyjście
Dla każdego zestawu danych wypisz w oddzielnym wierszu jedną liczbę, równą minimalnej
liczbie razy, kiedy Bajtazar będzie musiał zakładać strój.
Przykład
Dla danych wejściowych:
5
1 1
1
2 2
1 1
3 2
1 2 1
7 3
1 2 1 1 3 2 1
8 4
1 2 3 4 1 2 3 4
poprawną odpowiedzią jest:
1
1
2
4
7
Autor zadania: Adrian Jaskółka (zapożyczenie).