Calcolatrice rotta

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

Descrizione del problema

Francesco ha fatto cadere la sua calcolatrice, e ora non funziona più come dovrebbe! Gli unici tasti funzionanti sono il $-$, il $\times$, l'$1$ e il $2$. Per utilizzare la calcolatrice è costretto a partire dal numero $1$ o dal numero $2$ (premendo il tasto corrispondente) e applicare zero o più volte una delle $4$ possibili operazioni funzionanti:

• sottrarre $1$
• sottrarre $2$
• moltiplicare per $1$
• moltiplicare per $2$

Per fare uno scherzo ai suoi amici, vorrebbe raggiungere sulla calcolatrice il numero $N$. Quante operazioni deve fare al minimo per farlo?

Nota: premere il tasto $1$ o $2$ all'inizio conta come un'operazione, inoltre la calcolatrice è danneggiata quindi Francesco è costretto a partire sempre da $1$ o $2$ (non può ad esempio premere $2$ e poi $1$ per partire dal numero $21$) e le uniche operazioni ammesse sono quelle precedentemente elencate (non può per esempio moltiplicare o sottrarre $12$ o $21$).

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$.

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

dove $\mathtt{test}$ è il numero del caso di test (a partire da $1$) e l'intero $\mathtt{operazioni}$ è la risposta al caso di test: il minimo numero di operazioni necessarie per raggiungere $N$.

Assunzioni

• $T = 10$, nei file di input che scaricherai saranno presenti esattamente $10$ casi di test.
• $1 \le N \le 10^{18}$.

Esempi di input/output

---

Input:

2

2

5

13

---

Output:

Case #1: 1
Case #2: 5
Case #3: 6

---

Spiegazione

Nel primo caso d'esempio, Francesco può direttamente digitare il 2 quindi farà una sola operazione.

Nel secondo caso d'esempio, Francesco può:

• digitare $2$.
• moltiplicare per $2$ ottenendo $4$.
• moltiplicare per $2$ ottenendo $8$.
• sottrarre $2$ ottenendo $6$.
• sottrarre $1$ ottenendo $5$.

Facendo così un totale di $5$ mosse.

Nel terzo caso d'esempio, Francesco può:

• digitare $2$.
• moltiplicare per $2$ ottenendo $4$.
• moltiplicare per $2$ ottenendo $8$.
• moltiplicare per $2$ ottenendo $16$.
• sottrarre $2$ ottenendo $14$.
• sottrarre $1$ ottenendo $13$.

Facendo così un totale di $6$ mosse.