Because of necessary software maintenance, Jutge.org may not fully work on the 7 of may, from 8 to 10 CEST.

Paradas a boxes P49116

Statement

html

Si la carrera dura x kilómetros, y necesitas cambiar las ruedas cada p kilómetros, ¿cuántas veces tendrás que parar en boxes para cambiar neumáticos?

Entrada

Una línea con el número n<10000 de casos. Cada caso se describe en una línea, con los dos números enteros x>0 y k>0.

Salida

Escribe n líneas, con el número de paradas a boxes que necesitas hacer para acabar la carrera.

Puntuación

Test: 40 Puntos
Resuelve varias entradas con casos donde x, k < 10⁹, por lo que caben en un entero de 32 bits.

Test: 20 Puntos
Resuelve varias entradas con casos donde x, k < 10¹⁸, por lo que caben en un entero de 64 bits.

Public test cases

Input

2
305 30
300 30

Output

10
9

Input

3
1842942 8
1842942 1842943
1842942 1842941

Output

230367
0
1

Information