Caramelle ai Bambini

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: caramelle.c
• Scarica la traccia in C++: caramelle.cpp
• Scarica la traccia in C#: caramelle.cs
• Scarica la traccia in Go: caramelle.go
• Scarica la traccia in JavaScript: caramelle.html
• Scarica la traccia in Java: caramelle.java
• Scarica la traccia in Pascal: caramelle.pas
• Scarica la traccia in Python: caramelle.py
• Scarica la traccia in VisualBasic: caramelle.vb

Descrizione del problema

Tommaso sta organizzando un torneo di biliardino, con un ricco premio in caramelle. Il biliardino di Volterra è molto lungo, infatti possono giocarci squadre con un qualsiasi numero di giocatori.

Al torneo partecipano $N$ squadre, numerate da $0$ a $N-1$. L' $i$-esima squadra ha $V_i$ giocatori. Tommaso vuole decidere il montepremi in modo che qualsiasi squadra vinca sia in grado di distribuire le caramelle equamente fra i suoi membri, cioè dando a ciascuno lo stesso numero(intero) di caramelle, senza lasciarne alcuna non distribuita.

Qual è il minimo numero possibile di caramelle nel montepremi?

Dati 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 da $2$ righe:

• la prima riga contiene l'intero $N$;
• la seconda riga contiene gli $N$ interi $V_i$, per $0 \le i \le N-1$;

Dati 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: c

dove t è il numero del caso di test (a partire da $1$) e il valore c è il minimo numero di caramelle necessario.

Assunzioni

• $T = 8$, nei file di input che scaricherai saranno presenti esattamente $8$ casi di test.
• $1 \le N \le 1\,000$.
• $1 \le V_i \le 10^9$ per ogni $0 \le i \le N-1$.
• Per ogni testcase la risposta è $\le 10^9$.

Esempi di input/output

---

Input:

2

5
4 5 2 5 10

10
3 12 2 1 4 10 15 30 5 6

---

Output:

Case #1: 20
Case #2: 60

---

Spiegazione

Nel primo caso d'esempio la ci sono $N = 5$ squadre. Con $20$ caramelle è possibile soddisfare ogni squadra, infatti:

• è possibile dare $5$ caramelle a ognuno dei $4$ membri della squadra $0$.
• è possibile dare $4$ caramelle a ognuno dei $5$ membri della squadra $1$.
• è possibile dare $10$ caramelle a ognuno dei $2$ membri della squadra $2$.
• è possibile dare $4$ caramelle a ognuno dei $5$ membri della squadra $3$.
• è possibile dare $2$ caramelle a ognuno dei $10$ membri della squadra $4$.

Non è possibile distribuire equamente a ogni squadra un numero minore di caramelle.

Nel secondo caso d'esempio ci sono $N = 10$ squadre. Il minimo numero di caramelle necessarie per soddifsfare ogni squadra è $60$.

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 $V_{0}, \, \ldots, \, V_{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 #test: ", dove test è il numero del caso di test (a partire da $1$), seguita dall'intero $c$.