Problema número 607

Minimizando el castigo

Tiempo máximo: 2,000 sMemoria máxima: 4096 KiB
Tijeras sobre un teclado, con los agujeros de los dedos en la tecla Ctrl y teclas C y V

A Larry, un inquieto muchacho del Bronx, le pusieron en cierta ocasión como castigo en el Instituto escribir 100 veces "Lawrence Gordon Tesler no volverá a copiar". La frase resultaba francamente irónica pues al tenerla que repetir tantas veces no hacía otra cosa que… copiarla.

Aquel castigo le pareció un sinsentido de modo que decidió buscar un atajo. En aquella época ya existían las fotocopias, aunque por entonces aún se las conocía como xeroxcopias debido a la marca que las inventó e hizo populares*. Se le ocurrió que podía escribir la frase una sola vez, hacer una copia, recortarla y pegarla justo debajo de la original. Una vez que tuviera las dos juntas, podía hacer una nueva copia, recortarla, y poner, debajo de las anteriores, las dos nuevas frases. Con un poco de paciencia conseguiría tener las 100 frases "escritas" en un momento, y dedicar la tarde a algo más productivo.

Nadie pareció darse cuenta de la trampa, ni siquiera el profesor que, a la larga, marcaría su vida al introducirle en el mundo de la programación. Con el tiempo, ya trabajando en Xerox PARC, recordaría con cariño aquella tarde de fotocopias, tijeras y pegamento de barra que le inspiró para inventar el copiar y pegar.

Entrada

La entrada comienza con un número indicando cuántos casos de prueba deberán ser procesados. Cada uno será un número entre 1 y 109 indicando cuántas veces tiene Larry que escribir, como castigo, una determinada frase.

Salida

Por cada caso de prueba el programa escribirá el mínimo número de operaciones de fotocopia, recorte y pegado que tendrá que hacer Larry para terminar el castigo completo, partiendo de una única línea, escrita a mano, de la frase.

Entrada de ejemplo

4
1
2
3
4

Salida de ejemplo

0
1
2
2
1Curiosamente, Larry terminaría trabajando, durante más de 10 años, para Xerox.