* $1 ≤ T ≤ 10$
* $1 ≤ N ≤ 10^5^$

* Pentru teste in valoare de $20$ de puncte se garanteaza ca $N ≤ 20$
* Pentru teste in valoare de $50$ de puncte se garanteaza ca $N ≤ 1000$

* Pentru $20%$ din teste se garanteaza ca $N ≤ 20$
* Pentru alte $30%$ din teste se garanteaza ca $N ≤ 1000$

* O perla dintr-un colier cu o singura perla nu are niciun vecin
* O perla dintr-un colier cu doua perle are un singur vecin
* O perla dintr-un colier cu mai mult de doua perle are doi vecini