Problema número 736

Pasos en la escalera

Tiempo máximo: 1,000 sMemoria máxima: 4096 KiB
Escaleras de piedra

Pepa Taslargas tiene una capacidad envidiable: es capaz de subir varios escalones de una sola vez. Hay gente que puede subir de golpe dos escalones, pero para ella eso es de aficionados. Su habilidad la ha llevado a recorrer el mundo participando en las llamadas carreras verticales, como la carrera de torres más famosa y antigua del mundo en la que los participantes deben subir los 1576 escalones del Empire State Building.

Una persona normal necesitaría 1576 pasos para subir todos esos escalones. Subiéndolos de dos en dos, son suficientes 788 y de tres en tres solo 526.

Entrada

El primer número de la entrada indica cuántos casos de prueba deberán ser procesados.

A continuación aparece una línea por cada caso de prueba, con dos números entre 1 y 1.000.000. El primero indica el número de escalones de una escalera y el segundo cuántos escalones se pueden subir de una sola vez.

Salida

Por cada caso de prueba se escribirá el número mínimo de pasos necesarios para subir todos los peldaños.

Entrada de ejemplo

5
1576 1
1576 2
1576 3
4000 1999
3 4

Salida de ejemplo

1576
788
526
3
1