Gira la ruota

Attenzione: Questo task ha un tempo limite di 10 minuti per l'invio della soluzione. Una volta richiesto un input, il timer partirà in automatico, e dopo la scadenza non sarà più possibile inviare una soluzione per quell'input. È sempre possibile richiedere un nuovo input, per cui non preoccuparti se il timer scade: dovrai semplicemente richiedere e scaricare un nuovo input.

Per aiutarti con questo task, abbiamo preparato delle tracce di soluzione, che includono solo le parti di lettura dell'input e scrittura dell'output (da tastiera e su schermo). Puoi decidere se leggere/scrivere su file decommentando le opportune righe di codice.

• Scarica la traccia in C: ruota.c
• Scarica la traccia in C++: ruota.cpp
• Scarica la traccia in C#: ruota.cs
• Scarica la traccia in Go: ruota.go
• Scarica la traccia in JavaScript: ruota.html
• Scarica la traccia in Java: ruota.java
• Scarica la traccia in Pascal: ruota.pas
• Scarica la traccia in Python: ruota.py
• Scarica la traccia in VisualBasic: ruota.vb

Descrizione del problema

Una delle principali attrazioni della fattoria di Filippo e' la ruota della fortuna, un disco diviso in $N$ spicchi, ognuno di essi colorato con un colore da $0$ a $N-1$. L'$i$-esimo spicchio, in senso orario, e' del colore $R_i$.

Luca vorrebbe tantissimo girare la ruota, ma ha paura di far arrabbiare Filippo. Ha pensato quindi che se, dopo aver girato la ruota, essa non fosse distinguibile da prima nessuno si farebbe domande. Quanti sono gli interi $1 \le K \le N$ tali che la ruota girata di $\frac{K \cdot 360}{N}$ gradi in senso orario non sia distinguibile dalla ruota in posizione iniziale?

Formato di input

La prima riga del file di input contiene un intero $T$, il numero di casi di test. Seguono $T$ casi di test, numerati da $1$ a $T$. Ogni caso di test è preceduto da una riga vuota.

Ogni caso di test è composto come segue:

• una riga contenente l'intero $N$.
• una riga contenente gli $N$ interi $R_{0}, \, \ldots, \, R_{N-1}$.

Formato di output

Il file di output deve contenere la risposta ai casi di test che sei riuscito a risolvere. Per ogni caso di test che hai risolto, il file di output deve contenere una riga con la dicitura:

Case #t: K

dove t è il numero del caso di test (a partire da $1$) e il valore K è la tua risposta per il test t.

Assunzioni

• $T = 18$, nei file di input che scaricherai saranno presenti esattamente $14$ casi di test.
• $1 \le N \le 200000$
• $0 \le R_i < N$.

Nei primi $6$ casi di test vale $N\le 1000$.

Esempi di input/output

---

Input:

2

6
1 2 3 1 2 3

5
2 5 4 2 3

---

Output:

Case #1: 2
Case #2: 1

---

Spiegazione

Nel primo caso d'esempio è possibile girare la ruota di $180 = 3 \cdot \frac{360}{6}$ oppure $360 = 6 \cdot \frac{360}{6}$ gradi.

Nel secondo caso d'esempio è solo possibile girare la ruota di $360 = 5 \cdot \frac{360}{5}$ gradi.