SPOJ Brasil

A Segunda Guerra Mundial foi o confronto que causou mais vítimas na história da humanidade. Iniciando-se em 1939, ela opôs, de um lado, o Eixo, formado por Alemanha, Itália e Japão, e de outro os Aliados, que contavam, entre outros, com China, França, Inglaterra, Estados Unidos e Rússia. O Brasil se integrou aos Aliados em 1943, grupo esse que saiu vencedor em 1945.

Entre os principais nomes da guerra estavam Adolph Hitler, Benito Mussolini, Joseph Stalin e Winston Churchill. Porém, outras personalidades também tiveram seu destaque no período. Alguns desses passaram desconhecidos por várias décadas, mas documentos recentemente encontrados, mostraram que a atuação dessas pessoas tiveram um grande impacto no resultado final. Um desses ex-desconhecidos é o General da Gringolândia, Charles Eduard Blacksmith.

Charles era uma pessoa muito peculiar. Ele exigia que seus soldados sempre formassem uma fila, de tal maneira que pudesse vê-los todos ao mesmo tempo, para receber as ordens. Por ter uma estatura abaixo da média (usando um pouco de eufemismo), essa fila deveria estar em ordem crescente de altura dos soldados. Para evitar confusão, Little Charles, como era conhecido, sempre comandava seus soldados na hora deles se organizarem na fila. Porém, logo ele notou que para grandes batalhões essa era uma tarefa que dava muito trabalho. Para evitar a fadiga, ele, então, decidiu contratar terceiros para organizar a fila no seu lugar. Sua tarefa é, dada a fila inicial, com a altura de cada soldado, encontrar o menor número de trocas para organizá-la. Contudo, Charles impôs a seguinte condição: um soldado na posição i da fila só pode trocar de lugar com o soldado que está na posição i + k da fila. (um jeito bem peculiar, não?)

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.

Cada instância terá duas linhas. Na primeira haverá dois inteiros N e K que indicam o número de soldados e a distância entre dois soldados que podem trocar de posições, respectivamente. Na segunda haverão N inteiros separados por um espaço, com a altura de cada soldado, na ordem em que estão na fila inicialmente.

Restrições

1 <= N <= 100000
1 <= K <= N
1 <= ai <= 1000000 Altura do soldado i, onde i = 1, 2, . . . , N.

Saída

Para cada instância imprima um inteiro com o menor número de trocas necessárias para ordenar os soldados, ou impossivel caso não seja possível ordenar os soldados levando em conta a condição imposta por Little Charles.

Exemplo de entrada

3
4 2
3 4 1 2
4 1
4 3 2 1
4 2
7 3 6 5

Saída para o exemplo de entrada

2
6
impossivel