== include(page="template/taskheader" task_id="vegas") ==
Poveste şi cerinţă...
$Aceasta problema a fost preluată de pe atcoder:$ 'F - Prime Flip':https://atcoder.jp/contests/arc080/tasks/arc080_d*
Dl J. a ajuns săptămâna aceasta în Vegas. Dacă nu îl cunoașteți încă pe dl J., nu vă îngrijorați, tot ce trebuie să faceți pentru a intra în cercul lui de apropiați este să existați și să-l ajutați cu o mică problema, dar toate la timpul lor.
Jocul preferat al dlui J. este unul rezervat cunoscătorilor, așa că nu vă vom împovăra cu numele lui. Cât despre reguli, acestea sunt cum nu se poate mai simple. Pe o masa se află un număr infinit de cărți, numerotate de la 1. Inițial cărțile $x{~1~}, x{~2~}, ... x{~N~}$ se află cu fața în sus, iar toate celelalte sunt așezate cu fața în jos. Jucătorul poate aplica asupra cărților, de câte ori vrea, următoarea operație:
* Alege un număr prim $p ≥ 3$. Apoi alege $p$ cărți consecutive și le întoarce pe fiecare dintre ele.
Jucătorul câștigă dacă reușește să aducă toate cărțile cu fața în jos dintr-un număr minim de mutări.
Aici interveniți voi. Ajutați-l pe dl J. să afle care este numărul minim de mutări pentru a câștiga la o masă de joc dată!
h2. Date de intrare
Fişierul de intrare $vegas.in$ ...
Fişierul de intrare $vegas.in$ conține $T$ teste. Pe prima linie a fișierului se află $T$, numărul de teste din fișier.
Fiecare test este format din două linii. Prima dintre acestea conține $N$, numărul de cărți care se află cu fața în sus. Pe a doua linie a testului, se dau, în ordine crescătoare, separate prin spațiu, cele $N$ cărți.
h2. Date de ieşire
În fişierul de ieşire $vegas.out$ ...
În fişierul de ieşire $vegas.out$ se vor afișa $T$ linii. Pe a $i$-a linie afișați numărul minim de operații de care are nevoie dl J. pentru a câștiga la masa descrisă în al $i$-lea test din fișierul de intrare.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 6$
* $1 ≤ N ≤ 100$
* $1 ≤ x{~1~} < x{~2~} < ... < x{~N~} ≤ 10^7^$
h2. Subtask-uri
table(subtask-uri). |_. Subtask |_. Punctaj |_. Restricții |
| 1 | 1 punct | $1 ≤ N ≤ 10$ |
| 2 | 1 punct | $1 ≤ N ≤ 20$ |
| 3 | 1 punct | $1 ≤ x{~N~} ≤ 200$ |
| 4 | 2 puncte | Fără restricții adiționale |
h2. Exemplu
table(example). |_. vegas.in |_. vegas.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 2
2
1 2
6
3 4 5 6 7 9
| 2
4
|
h3. Explicaţie
...
În primul test din exemplu, prima operație este să întoarcă secvența de cărți 1-5 => cărțile cu fața în sus vor fi: 3, 4, 5.
A doua operație este să întoarcă cărțile din secvența 3-5 => toate cărțile ajung cu fața în jos.
Al doilea test din exemplu:
După secvența: 8-12 => cărțile cu fața în sus: 3 4 5 6 7 8 10 11 12
După secvența: 10-12 => cărțile cu fața în sus: 3 4 5 6 7 8
După secvența: 3-13 => cărțile cu fața în sus: 9 10 11 12 13
După secvența: 9-13 => toate cărțile sunt cu fața în jos
== include(page="template/taskfooter" task_id="vegas") ==
