Condividi il cioccolato

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

Descrizione del problema

Lorenzo adora il cioccolato, e allora si è comprato una tavoletta di cioccolato fatta di $N \times M$ quadratini. Anche i $K$ suoi compagni di classe vorrebbero mangiare il cioccolato, e Lorenzo è troppo buono per non dargliene! Quindi per $K$ volte spezza la tavoletta in due parti rettangolari, non necessariamente uguali, e dà una delle due ad uno dei suoi $K$ compagni tenendo infine l'ultimo pezzo per sè.

La tavoletta può essere spezzata solo lungo i bordi dei quadratini, in orizzontale o verticale, in modo tale da non dividere nessun quadratino in due. Inoltre una volta spezzata una parte, quella viene subito presa e mangiata da un amico senza dargli la possibilità di spezzarla ulteriormente. Lorenzo vorrebbe sapere come spezzare la tavoletta $K$ volte in modo che gli rimangano il maggior numero possibile di quadratini, sai aiutarlo a capire quanti quadratini di cioccolato terrà alla fine per se?

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 i tre interi a 64 bit $N$, $M$, $K$.

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: risposta"

dove $\mathtt{test}$ è il numero del caso di test (a partire da $1$) e l'intero a 64 bit $\mathtt{risposta}$ è il numero di cioccolatini che rimangono a Lorenzo.

Assunzioni

• $T = 10$, nei file di input che scaricherai saranno presenti esattamente $10$ casi di test.
• $1 \le N, M \le 10^{12}$.
• nei primi $8$ subtask $1 \le N, M \le 10^9$.
• $N + M > 2$
• $1 \le K \le (N + M - 2)$.
• è garantito che la risposta sia minore di $10^{18}$.

Esempi di input/output

---

Input:

2

3 2 1

4 6 3

---

Output:

Case #1: 4
Case #2: 12

---

Spiegazione

Nel primo caso d'esempio, Lorenzo può spezzare la tavoletta in due pezzi: uno di dimensione $1 \times 2$ e uno di dimensione $2 \times 2$. Tiene quindi per sè il secondo pezzo formato da $4$ quadratini.

Nel secondo caso d'esempio, Lorenzo può:

• spezzare la tavoletta in due pezzi: uno di dimensione $4 \times 1$ e uno di dimensione $4 \times 5$ e consegnare al primo compagno il primo pezzo.
• spezzare il pezzo $4 \times 5$ in due pezzi: uno di dimensione $4 \times 1$ e uno di dimensione $4 \times 4$ e consegnare al secondo compagno il primo pezzo.
• spezzare il pezzo $4 \times 4$ in due pezzi: uno di dimensione $3 \times 4$ e uno di dimensione $1 \times 4$ e consegnare al terzo compagno il secondo pezzo.

Alla fine, il numero di quadratini che rimangono a Lorenzo è $3 \times 4 = 12$.