Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MWP5_2C - Przemytnicy

Na granicy polsko-ukraińskiej rozwinął się na szeroką skalę nowy niepokojący proceder - przemyt liczb. Każdy z przemytników może jednorazowo zabrać ze sobą tylko jedną liczbę, toteż całymi dniami kursują piechotą raz w jedną, a raz w drugą stronę całe rzesze ludzi żądnych zysku. O ile przemyt zwykłej liczby jest uznawany za mało szkodliwy społecznie i celnicy na ogół przymykają na niego oko, o tyle przemyt liczby pierwszej to poważne wykroczenie karane z całą surowością.

Siatka przemytników liczb pierwszych, na całe szczęście, jest już dosyć mocno rozpracowana i służby celne mają w niej swoich tajnych agentów. Tajni agenci nie marnują czasu i właśnie dostarczyli listę zawierającą liczby jakie przemycane będą jutro przez granicę. Z listy jasno wynika, że szykowana jest duża partia liczb pierwszych i celnicy szykują w związku z tym operację zakrojoną na szeroką skalę. Ich plan jest prosty - n celników wyskoczy ze swojej budki w najlepszym do tego momencie i złapie n kolejnych przemytników - każdy łapie tylko jednego, co ostatecznie jest nawet logiczne... Plan ma tylko jeden mały feler - celnicy nie mają pojęcia, który moment będzie najlepszy i ilu przemytników z liczbami pierwszymi uda im się zatrzymać. Pomóż im, napisz program, który na podstawie kolejnych liczb jakie przemycane będą jutro przez granicę ustali ile maksymalnie liczb pierwszych zatrzyma n-ta liczba celników, jeżeli rozpoczną operację w najlepszym do tego momencie.

Wejście

W pierwszej linii wejścia znajduje się liczba t (1 ≤ t ≤ 1000) określająca ilość zestawów danych. Każdy zestaw składa się z dwóch linii. Pierwsza z nich zawiera liczby m (1 ≤ m ≤ 1000) oraz n (1 ≤ n ≤ 100) oznaczające odpowiednio liczbę przemytników jaka przejdzie jutro przez granicę oraz liczbę celników jaka będzie uczestniczyć w akcji. Druga linia zawiera m liczb z zakresu od 0 do 106 - są to przemycane liczby (k-ta osoba przemyca k-tą liczbę).

Wyjście

Na wyjściu należy w oddzielnej linii dla każdego zestawu danych wypisać jedną liczbę - określającą ilu przemytników liczb pierwszych uda się zatrzymać w trakcie akcji.

Podsumowując dla danych wczytanych na wejściu należy wyznaczyć ile liczb pierwszych maksymalnie może znaleźć się w podciągu spójnym o długości nie przekraczającej n.

Przykład

Wejście:

2
8 4
3 8 6 5 4 4 7 7
9 5
9 6 12 7 4 5 3 2 4

Wyjście:

2
4

Dodane przez:Maciej Boniecki
Data dodania:2013-03-15
Limit czasu wykonania programu:0.5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 SCM qobi
Pochodzenie:V Mistrzostwa WWSI w Programowaniu

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.