ODI - Prácticas

Ana es profesora del segundo año de primaria.  Ella está preparado un viaje de excursión con su curso para este fin de semana.  Como el viaje es largo, los estudiantes se impacientan.  Para mantener el grupo calmado, Ana tiene varias cajas de dulces, y cada una de estas cajas tiene exactamente la misma cantidad de dulces que las demás.  

Si no se permite descartar ningún dulce ni dejar fuera ningún estudiante, cuántas cajas adicionales de dulce Ana debe comprar para repartir equitativamente los dulces entre todos lo estudiantes?

Entrada

La primera línea de entrada contiene un número entero C (1 ≤ C ≤ 5), la cantidad de casos de pruebas a procesar.

Cada una de las siguientes C líneas contiene 3 números enteros separados por un espacio en blanco. Los números son, en orden:

• N (1 ≤  N ≤  1,000,000,000), la cantidad de estudiantes del curso

• B (0 ≤  B ≤  100), la cantidad de cajas de dulces que Ana tiene inicialmente

• K (1 ≤ K ≤  1,000), la cantidad de dulces en cada caja de dulces

Por lo menos 20% de los casos de pruebas tendrá N ≤  1,000,000.

Por lo menos 20% de los casos de pruebas tendrá B = 0.

Salida

Por cada caso de prueba, imprime una línea con la cantidad mínima de cajas que Ana debe comprar para repartir igual cantidad de dulces a cada estudiante de su curso.  Si no es posible hacer esta distribución equitativa, imprime -1.  La i-ésima línea debe corresponder con el i-ésimo caso de prueba.

Ejemplo