== include(page="template/taskheader" task_id="aiacubile") ==

Cangurul Bulănel trebuie să aibă grijă de $N$ copii. Pentru a nu se plictisi, acesta s-a gândit la un joc să se joace împreună cu ei.
Cangurul Bulănel aşează copiii într-un cerc şi le atribuie câte un număr de la $1$ la $N$. Poziţiile pe care sunt aşezaţi copiii sunt de asemenea numerotate de la $1$ la $N$. Fiind în cerc, fiecare poziţie are o poziţie succesoare: după $1$ urmează $2$, după $2$ urmează $3$, ... după $N-1$ urmează $N$, după $N$ urmează $1$. Iniţial, fiecare copil se aşează pe poziţia egală cu indicele său: copilul $1$ se aşează pe poziţia $1$, copilul $2$ se aşează pe poziţia $2$, ... copilul $N$ se aşează pe poziţia $N$.
Jocul se desfăşoară pe parcursul mai multor ture. O tură a jocului se desfăşoară astfel: cangurul Bulănel porneşte de pe poziţia $1$ şi sare din $K$ în $K$ poziţii până când ajunge pe o poziţie pe care a mai fost în tura respectivă. Copiii aşezaţi pe poziţiile vizitate de Bulănel primesc de la acesta câte o bilă. La finalul turei, copiii îşi schimbă ordinea în felul următor: un copil aflat pe poziţia $i$ se mută pe poziţia $P[i]$. După ce toţi copiii îşi schimbă ordinea, începe o nouă tură a jocului după cum a fost descrisă anterior.
De exemplu, dacă considerăm că jocul se joacă cu $N = 6$ copii, iar cangurul Bulănel sare $K = 2$ poziţii, atunci:

Cangurul Bulănel trebuie să aibă grijă de N copii. Pentru a nu se plictisi, acesta s-a gândit la un joc să se joace împreună cu ei.
Cangurul Bulănel aşează copiii într-un cerc şi le atribuie câte un număr de la 1 la N. Poziţiile pe care sunt aşezaţi copiii sunt de asemenea numerotate de la 1 la N. Fiind în cerc, fiecare poziţie are o poziţie succesoare: după 1 urmează 2, după 2 urmează 3, ... după N-1 urmează N, după N urmează 1. Iniţial, fiecare copil se aşează pe poziţia egală cu indicele său: copilul 1 se aşează pe poziţia 1, copilul 2 se aşează pe poziţia 2, … copilul N se aşează pe poziţia N.
Jocul se desfăşoară pe parcursul mai multor ture. O tură a jocului se desfăşoară astfel: cangurul Bulănel porneşte de pe poziţia 1 şi sare din K în K poziţii până când ajunge pe o poziţie pe care a mai fost în tura respectivă. Copiii aşezaţi pe poziţiile vizitate de Bulănel primesc de la acesta câte o bilă. La finalul turei, copiii îşi schimbă ordinea în felul următor: un copil aflat pe poziţia i se mută pe poziţia P[i]. După ce toţi copiii îşi schimbă ordinea, începe o nouă tură a jocului după cum a fost descrisă anterior.
De exemplu, dacă considerăm că jocul se joacă cu N = 6 copii, iar cangurul Bulănel sare K = 2 poziţii, atunci:

| !problema/aiacubile?01.jpg! | !problema/aiacubile?02.jpg! | !problema/aiacubile?03.jpg! | !problema/aiacubile?04.jpg! |

| Copiii sunt aşezaţi în cerc iniţial. Bulănel începe de pe poziţia $1$ şi îi lasă copilului $1$ o bilă. | Bulănel sare $2$ poziţii, ajunge pe poziţia $3$ şi îi lasă copilului $3$ o bilă. | Bulănel sare $2$ poziţii, ajunge pe poziţia $5$ şi îi lasă copilului $5$ o bilă. | Bulănel sare $2$ poziţii, ajunge pe poziţia $1$. Deoarece a mai vizitat poziţia $1$ în tura curentă, se opreşte. |

| Copiii sunt aşezaţi în cerc iniţial. Bulănel începe de pe poziţia 1 şi îi lasă copilului 1 o bilă. | Bulănel sare 2 poziţii, ajunge pe poziţia 3 şi îi lasă copilului 3 o bilă. | Bulănel sare 2 poziţii, ajunge pe poziţia 5 şi îi lasă copilului 5 o bilă. | Bulănel sare 2 poziţii, ajunge pe poziţia 1. Deoarece a mai vizitat poziţia 1 în tura curentă, se opreşte. |

La finalul turei, copiii $1$, $3$ şi $5$ au primit câte o bilă. Înainte de începerea turei următoare, copiii îşi schimbă poziţiile altfel: dacă pentru jocul acesta considerăm şirul $P$ ca fiind $5 3 1 6 2 4$, atunci copilul de pe poziţia $1$ (copilul $1$) se va muta pe poziţia $5$, copilul de pe poziţia $2$ (copilul $2$) se va muta pe poziţia $3$, copilul de pe poziţia $3$ (copilul $3$) se va muta pe poziţia $1$, copilul de pe poziţia $4$ (copilul $4$) se va muta pe poziţia $6$, copilul de pe poziţia $5$ (copilul $5$) se va muta pe poziţia $2$, iar copilul de pe poziţia $6$ (copilul $6$) se va muta pe poziţia $4$. Aşadar, pe fiecare poziţie de la $1$ la $6$ o să se afle, în ordine, copiii $3 5 2 6 1 4$. Cangurul Bulănel va sări pe poziţiile $1$, $3$ şi $5$ şi va lăsa câte o bilă copiilor $3$, $2$ şi $1$.

La finalul turei, copiii 1, 3 şi 5 au primit câte o bilă. Înainte de începerea turei următoare, copiii îşi schimbă poziţiile altfel: dacă pentru jocul acesta considerăm şirul P ca fiind 5 3 1 6 2 4, atunci copilul de pe poziţia 1 (copilul 1) se va muta pe poziţia 5, copilul de pe poziţia 2 (copilul 2) se va muta pe poziţia 3, copilul de pe poziţia 3 (copilul 3) se va muta pe poziţia 1, copilul de pe poziţia 4 (copilul 4) se va muta pe poziţia 6, copilul de pe poziţia 5 (copilul 5) se va muta pe poziţia 2, iar copilul de pe poziţia 6 (copilul 6) se va muta pe poziţia 4. Aşadar, pe fiecare poziţie de la 1 la 6 o să se afle, în ordine, copiii 3 5 2 6 1 4. Cangurul Bulănel va sări pe poziţiile 1, 3 şi 5 şi va lăsa câte o bilă copiilor 3, 2 şi 1.

Jocul se termină când copiii ajung la ordinea de la care au pornit iniţial.
h2. Cerinţă

Cangurul Bulănel doreşte să joace mai multe astfel de jocuri. Pentru fiecare joc, cunoscându-se numărul $N$ de copii, lungimea $K$ reprezentând numărul de poziţii pe care cangurului Bulănel le poate sări şi şirul $P$ care descrie felul în care copiii îşi schimbă poziţiile la fiecare tură, să se afle câţi copii primesc cel puţin o bilă pe parcursul întregului joc.

Cangurul Bulănel doreşte să joace mai multe astfel de jocuri. Pentru fiecare joc, cunoscându-se numărul N de copii, lungimea K reprezentând numărul de poziţii pe care cangurului Bulănel le poate sări şi şirul P care descrie felul în care copiii îşi schimbă poziţiile la fiecare tură, să se afle câţi copii primesc cel puţin o bilă pe parcursul întregului joc.

h2. Date de intrare

Fişierul de intrare aiacubile.in conţine pe prima linie numărul natural $T$, reprezentând numărul de jocuri la care cangurul Bulănel participă. Următoarele $2*T$ linii descriu cele $T$ jocuri în felul următor: pe linia $2*i-1$ se află numerele naturale $N$ şi $K$, cu semnificaţia din enunţ, iar pe linia $2*i$ se află $N$ numere naturale ce formează şirul $P$, ce descrie cum îşi schimbă copiii ordinea la fiecare tură, pentru al $i$-lea joc.

Fişierul de intrare aiacubile.in conţine pe prima linie numărul natural T, reprezentând numărul de jocuri la care cangurul Bulănel participă. Următoarele 2*T linii descriu cele T jocuri în felul următor: pe linia 2*i-1 se află numerele naturale N şi K, cu semnificaţia din enunţ, iar pe linia 2*i se află N numere naturale ce formează şirul P, ce descrie cum îşi schimbă copiii ordinea la fiecare tură, pentru al i-lea joc.

h2. Date de ieşire

Fişierul de ieşire aiacubile.out va conţine $T$ linii. Fiecare linie conţine câte un număr natural care reprezintă numărul de copii ce au primit măcar o bilă pe parcursul celui de-al $i$-lea joc.

Fişierul de ieşire aiacubile.out va conţine T linii. Fiecare linie conţine câte un număr natural care reprezintă numărul de copii ce au primit măcar o bilă pe parcursul celui de-al i-lea joc.

h2. Restricţii

* Pentru toate testele, $1 ≤ T ≤ 10$.
* Pentru toate testele, $1 ≤ P[i] ≤ N$, iar şirul $P$ conţine doar numere distincte.

* Pentru toate testele, 1 ≤ T ≤ 10.
* Pentru toate testele, 1 ≤ P[i] ≤ N, iar şirul P conţine doar numere distincte.

* Se garantează că, la orice moment al oricărui joc, o să fie exact un copil pe fiecare poziţie.

* Pentru teste în valoare de $20$ de puncte, $1 ≤ N ≤ 1 000$, iar numărul de ture pe care le are fiecare joc se garantează că este $≤ 1 000$.
* Pentru teste în valoare de $90$ de puncte, $1 ≤ N ≤ 100 000$.
* Problema va fi evaluată pe teste în valoare de $90$ de puncte.
* Se vor acorda $10$ puncte din oficiu.

* Pentru teste în valoare de 20 de puncte, 1 ≤ N ≤ 1 000, iar numărul de ture pe care le are fiecare joc se garantează că este ≤ 1 000.
* Pentru teste în valoare de 90 de puncte, 1 ≤ N ≤ 100 000.
* Problema va fi evaluată pe teste în valoare de 90 de puncte.
* Se vor acorda 10 puncte din oficiu.

h2. Exemplu

| 2
6 2
5 3 1 6 2 4

4

12 9
1 6 7 4 9 8 3 12 10 11 5 2
| 4

h3. Explicaţie
Explicaţie pentru primul joc:

În prima tură de joc, copiii sunt în ordinea $1 2 3 4 5 6$. Copiii $1$, $3$ şi $5$ primesc câte o bilă (ca în enunţ).
În a doua tură de joc, copiii sunt în ordinea $3 5 2 6 1 4$. Copiii $3$, $2$ şi $1$ primesc câte o bilă (ca în enunţ).
În a treia tură de joc, copiii sunt în ordinea $2 1 5 4 3 6$. Copiii $2$, $5$ şi $3$ primesc câte o bilă.
În a patra tură de joc, copiii sunt în ordinea. $5 3 1 6 2 4$. Copiii $5$, $1$ şi $2$ primesc câte o bilă.
În a cincea tură de joc, copiii sunt în ordinea $1 2 3 4 5 6$. Fiind ordinea iniţială, jocul se opreşte. Copiii $1$, $2$, $3$ şi $5$ au primit măcar câte o bilă pe parcursul jocului, aşa că răspunsul pentru primul joc este $4$.

În prima tură de joc, copiii sunt în ordinea 1 2 3 4 5 6. Copiii 1, 3 şi 5 primesc câte o bilă (ca în enunţ).
În a doua tură de joc, copiii sunt în ordinea 3 5 2 6 1 4. Copiii 3, 2 şi 1 primesc câte o bilă (ca în enunţ).
În a treia tură de joc, copiii sunt în ordinea 2 1 5 4 3 6. Copiii 2, 5 şi 3 primesc câte o bilă.
În a patra tură de joc, copiii sunt în ordinea. 5 3 1 6 2 4. Copiii 5, 1 şi 2 primesc câte o bilă.
În a cincea tură de joc, copiii sunt în ordinea 1 2 3 4 5 6. Fiind ordinea iniţială, jocul se opreşte. Copiii 1, 2, 3 şi 5 au primit măcar câte o bilă pe parcursul jocului, aşa că răspunsul pentru primul joc este 4.

Pentru al doilea joc, copiii $1, 3, 4, 5, 7, 9, 10, 11$ sunt cei care primesc bile, deci răspunsul este $8$.

Pentru al doilea joc, copiii 1, 3, 4, 5, 7, 9, 10, 11 sunt cei care primesc bile, deci răspunsul este 8.

== include(page="template/taskfooter" task_id="aiacubile") ==