Pesci alieni

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: pesci.c
• Scarica la traccia in C++: pesci.cpp
• Scarica la traccia in Python: pesci.py
• Scarica la traccia in Pascal: pesci.pas
• Scarica la traccia in Rust: pesci.rs
• Scarica la traccia in Java: pesci.java
• Scarica la traccia in JavaScript (Node.js): pesci.js

Descrizione del problema

L'ultima missione segreta della NASA su Encelado ha riportato a terra un campione del suo oceano sotterraneo, e con grande stupore vi sono state trovate $N$ uova di pesci alieni! L'allevamento di questi strani pesci è stato affidato a Monica, che li ha messi nel suo laghetto personale.

Questi pesci hanno un ciclo vitale molto rapido: al sorgere del sole, le uova si schiudono e i pesci iniziano a crescere. Durante il pomeriggio, i pesci si assembrano fino a formare più gruppi possibile di esattamente $K$ pesci ciascuno. Esattamente alle 5 del pomeriggio, ogni gruppo si accoppia creando un uovo, mentre eventuali pesci rimasti soli restano a guardare. Subito dopo, Monica raccoglie tutti i pesci nel laghetto e li porta ai laboratori per essere studiati, lasciando le uova nel laghetto per il giorno successivo. Qual è il numero totale di pesci che Monica potrà portare ai laboratori, dall'inizio fino alla loro totale estinzione?

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 una singola riga contenente due numeri interi separato da uno spazio. Il primo numero intero è $N$, il numero di uova di pesci alieni inizialmente presenti. il secondo numero intero è $K$, il numero di pesci che formano ogni gruppo di accoppiamento.

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: s

dove t è il numero del caso di test (a partire da $1$) e il valore s è il numero totale di pesci che Monica può portare ai laboratori in questo caso di test.

Assunzioni

• $T = 6$, nei file di input che scaricherai saranno presenti esattamente $6$ casi di test.
• $0 \le N \le 10^9$.
• $2 \le K \le 10^9$.

Esempi di input/output

Input:

2

7 2

2 7

Output:

Case #1: 11
Case #2: 2

Spiegazione

Nel primo caso d'esempio Monica ha a disposizione $7$ uova di pesci alieni, e sa che $2$ pesci sono necessari per formare un gruppo di accoppiamento:

• il primo giorno, vengono deposte $3$ uova da $6$ dei $7$ pesci che vengono poi portati al laboratorio;
• il secondo giorno, viene deposto un singolo uovo da $2$ dei $3$ pesci che vengono poi portati al laboratorio;
• il terzo giorno non viene deposto nessun uovo, e l'ultimo pesce viene portato al laboratorio.

In totale, Monica porta quindi ai laboratori $7 + 3 + 1 = 11$ pesci.

Nel secondo caso d'esempio Monica ha a disposizione $2$ uova e sa che $7$ pesci sono necessari per creare un uovo. Essendo che non ci sono abbastanza pesci per poter deporre alcun uovo, Monica porta $2$ pesci al laboratorio in totale.