Luke, an intergalactic traveller went on a trip across the universe and got candies from the different planets he visited. He comes back with $N$ candies and decides to distribute them among his $M$ friends. However, Luke only wants a fair distribution of the candies as he loves everyone equally. (A fair distribution is one in which each of his friends receive an equal number of candies and each friend receives at least one candy.) If a fair distribution is not possible, he might throw away some candies and try to distribute the remaining candies in a similar manner.
 
If he can throw away exactly $K$ candies at a time (he can throw away candies multiple times), what is the minimum number of times he will need to throw away candies before achieving a fair distribution?
 
------ Input: ------
 
First line will contain $T$, number of testcases. Then the testcases follow.
Each testcase contains of a single line of input, three integers $N, M, K$.
 
------ Output: ------
For each testcase, output a single integer denoting the minimum number of times he will need to throw away candies before achieving a fair distribution. If a fair distribution is not possible, print   -1.
 
------ Constraints ------
$1 ≤ T ≤ 10^{5}$
$2 ≤ N,M,K ≤ 10^{9}$

----- Sample Input 1 ------ 
2     
28 6 2       
78 5 3
----- Sample Output 1 ------ 
2
1
----- explanation 1 ------ 
Test case 1: There are 28 candies and 6 friends. He can distribute 24 candies fairly among his friends, each getting 4 candies. He then throws away the remaining 4 candies 2 at a time.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
def solve():
	(n, m, k) = map(int, input().rstrip().split())
	if n < m:
		return -1
	for i in range(n // m, 0, -1):
		if (n - m * i) % k == 0:
			return (n - m * i) // k
	return -1
for _ in range(int(input())):
	print(solve())


import sys

def solve():
	(n, m, k) = map(int, input().rstrip().split())
	if n < m:
		return -1
	left = n // m
	for i in range(left, 0, -1):
		t = n - m * i
		if t % k == 0:
			return t // k
	return -1
for _ in range(int(input())):
	print(solve())


for t in range(int(input())):
	(n, m, k) = map(int, input().split())
	i = 0
	count = 0
	while n > 0:
		if n % m == 0:
			i = 1
			break
		count += 1
		n -= k
	if i == 1:
		print(count)
	else:
		print(-1)


import sys
from collections import Counter, deque
from math import gcd, sqrt, ceil

def li():
	return [int(i) for i in sys.stdin.readline().split()]

def si():
	return sys.stdin.readline().split()

def ii():
	return int(sys.stdin.readline())

def ip():
	return sys.stdin.readline()[:-1]
for tastcas in range(int(input())):
	(n, m, k) = li()
	rem = []
	c = 0
	r = n % m
	if r == 0:
		print(c)
		continue
	rem.append(r)
	c += 1
	n -= k
	while n > 0:
		r = n % m
		if r == rem[0] or r == 0:
			rem.append(r)
			break
		c += 1
		n -= k
	if n > 0 and rem[-1] == 0:
		print(c)
	else:
		print(-1)


from math import gcd

def mod_inverse_helper(a, b):
	if b == 0:
		return (1, 0)
	small = mod_inverse_helper(b, a % b)
	x = small[1]
	y = small[0] - a // b * small[1]
	return (x, y)

def mod_inverse(a, b):
	ans = mod_inverse_helper(a, b)
	return (ans[0] + b) % b
t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	ans = 0
	if n < m or n % gcd(m, k) != 0:
		ans = -1
	else:
		g = gcd(m, k)
		n //= g
		m //= g
		k //= g
		inv = n * mod_inverse(k, m) % m
		if n - k * inv < m:
			ans = -1
		else:
			ans = inv
	print(ans)


def gcd(a, b):
	if b > a:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)

def snek(a, b):
	if b == 0:
		return (1, 0)
	s = snek(b, a % b)
	x = s[1]
	y = s[0] - a // b * s[1]
	return (x, y)

def snak(a, b):
	ans = snek(a, b)
	return (ans[0] + b) % b
t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	ans = 0
	if n < m or n % gcd(m, k) != 0:
		ans = -1
	else:
		g = gcd(m, k)
		n //= g
		m //= g
		k //= g
		c = n * snak(k, m) % m
		if n - k * c < m:
			ans = -1
		else:
			ans = c
	print(ans)


def gcd(a, b):
	if b > a:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)

def mod_inverse_helper(a, b):
	if b == 0:
		return (1, 0)
	small = mod_inverse_helper(b, a % b)
	x = small[1]
	y = small[0] - a // b * small[1]
	return (x, y)

def mod_inverse(a, b):
	ans = mod_inverse_helper(a, b)
	return (ans[0] + b) % b
t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	ans = 0
	if n < m or n % gcd(m, k) != 0:
		ans = -1
	else:
		check = False
		while n > 0:
			if n % m == 0:
				check = True
				break
			ans += 1
			n -= k
		if check == False:
			ans = -1
	print(ans)


for t in range(int(input())):
	(n, m, k) = map(int, input().split())
	x = n % m
	f = 0
	c = 0
	while n > 0:
		if n % m == 0:
			f = 1
			break
		c += 1
		n -= k
	if f == 1:
		print(c)
	else:
		print('-1')


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	x = n % m
	flag = False
	cnt = 0
	while n > 0:
		if n % m == 0:
			flag = True
			break
		cnt += 1
		n -= k
	if flag:
		print(cnt)
	else:
		print(-1)


def calc(n, m, k):
	count = 0
	while n % m != 0:
		n -= k
		count += 1
		if n <= 0:
			return -1
			break
	return count
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	print(calc(n, m, k))


from math import *
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	if n < m:
		print(-1)
	else:
		cnt = 0
		while n > 0:
			if n % m == 0:
				print(cnt)
				break
			else:
				cnt += 1
				n -= k
		else:
			print(-1)


def fun1(n, m, k):
	result = 0
	while n % m != 0:
		result += 1
		n -= k
		if n <= 0:
			return -1
	return result
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	print(fun1(n, m, k))


def count(n, m, k):
	c = 0
	while n % m != 0:
		c += 1
		n -= k
		if n <= 0:
			return -1
	return c
T = int(input())
for _ in range(T):
	(n, m, k) = map(int, input().split())
	print(count(n, m, k))


for i in range(int(input())):
	(n, m, k) = map(int, input().split())
	c = 0
	fg = 0
	while n % m != 0:
		n = n - k
		c = c + 1
		if n < m:
			fg = 1
			print(-1)
			break
	if fg == 0:
		print(c)


def share(candies, friends, dump):
	x = 0
	while candies % friends != 0:
		candies -= dump
		x += 1
		if friends > candies:
			return -1
	return x
for x in range(int(input())):
	data = str(input()).split(' ')
	print(share(int(data[0]), int(data[1]), int(data[2])))


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	if n % m == 0:
		print(0)
	elif m > n:
		print(-1)
	elif k > n:
		print(-1)
	else:
		count = 0
		printed = False
		while n > 0:
			if n % m == 0:
				print(count)
				printed = True
				break
			else:
				count += 1
				n -= k
		if not printed:
			print(-1)


t = int(input())
for i in range(t):
	x = input().split()
	a = int(x[0])
	b = int(x[1])
	c = int(x[2])
	flag = 0
	cn = 0
	while flag == 0 and b <= a:
		if a % b == 0:
			flag = 1
			print(cn)
			break
		else:
			a -= c
			cn += 1
	if flag == 0:
		print('-1')


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	t = False
	c = 0
	while n >= m:
		if n % m == 0:
			t = True
			break
		n = n - k
		c += 1
	if t:
		print(c)
	else:
		print(-1)


for __ in range(int(input())):
	(n, m, k) = map(int, input().split())
	count = 0
	if n % m == 0:
		print(0)
	else:
		t = n % m
		if t % k == 0:
			print(t // k)
		else:
			x = False
			while t < n:
				if t % k == 0:
					print(t // k)
					x = True
					break
				t += m
			if x == False:
				print(-1)


t = int(input())
if t < 100000:
	while t:
		t = t - 1
		(n, m, k) = map(int, input().split())
		if m > n:
			print(-1)
		else:
			(r, c) = (0, 0)
			while n >= m:
				if n % m == 0:
					r = 1
					print(c)
					break
				else:
					n = n - k
					c = c + 1
			if r == 0:
				print(-1)


for _ in range(int(input())):
	(c, f, t) = map(int, input().split())
	k = 0
	if c < f:
		print(-1)
	else:
		r = 0
		while c >= f:
			if c % f == 0:
				print(k)
				r = 1
				break
			else:
				k += 1
				c = c - t
		if r == 0:
			print(-1)


for _ in range(int(input())):
	(n, m, y) = map(int, input().split())
	if m > n:
		print(-1)
	else:
		(r, c) = (0, 0)
		while n >= m:
			if n % m == 0:
				r = 1
				print(c)
				break
			else:
				n = n - y
				c = c + 1
		if r == 0:
			print(-1)


import math
for i in range(int(input())):
	(n, m, k) = map(int, input().split())
	count = -1
	if n == m or n % m == 0:
		count = 0
	elif n > m:
		b = n / m
		c = math.floor(b)
		while c != 0:
			temp = n - m * c
			if temp % k == 0:
				count = temp // k
				break
			c -= 1
	else:
		count = -1
	print(count)


t = int(input())
for _ in range(t):
	[n, m, k] = [int(v) for v in input().strip().split()]
	if n < m:
		print('-1')
	elif n % m == 0:
		print('0')
	elif k > n - m:
		print('-1')
	else:
		flag = 0
		m_ = int(n / m)
		sub = m * int(n / m)
		ans = 0
		while flag == 0:
			if m_ <= 0:
				break
			if (n - sub) % k == 0:
				ans = n - sub
				flag = 1
				break
			else:
				m_ -= 1
				sub = m_ * m
				ans += 1
		if flag == 0:
			print('-1')
		else:
			print(int(ans / k))


for __ in range(int(input())):
	(n, m, k) = map(int, input().split())
	count = 0
	flag = 1
	while n >= m and flag:
		if n % m == 0:
			print(count)
			flag = 0
			break
		n = n - k
		count += 1
	if flag == 1:
		print('-1')


t = int(input())
while t > 0:
	(N, M, K) = list(map(int, input().split()))
	count = 0
	while N > 0:
		if N % M == 0:
			break
		N = N - K
		count += 1
	if N <= 0:
		print(-1)
	else:
		print(count)
	t -= 1


import math
for _ in range(int(input())):
	(n, m, k) = [int(x) for x in input().split()]
	count = 0
	while n > 0:
		if n % m == 0:
			break
		n = n - k
		count += 1
	if n <= 0:
		print(-1)
	else:
		print(count)


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	if m > n:
		print(-1)
	else:
		s = n
		f = 0
		count = 0
		while n >= m:
			if n % m == 0:
				f = 1
				print(count)
				break
			else:
				n = n - k
				count += 1
		if f == 0:
			print(-1)


def candy(a, b, c):
	s = 0
	while a % b != 0 and a > 0:
		a -= c
		s += 1
	if a <= 0:
		return -1
	return s
r = []
t = int(input())
for i in range(t):
	a = input().split()
	a = [int(i) for i in a]
	r += [candy(a[0], a[1], a[2])]
for i in r:
	print(i)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	c = 0
	while n % m and n > 0:
		n = n - k
		c += 1
	if n <= 0:
		print(-1)
	else:
		print(c)


for i in range(int(input())):
	(n, m, k) = [int(x) for x in input().split()]
	if n < m:
		print(-1)
	else:
		g = 0
		c = 0
		while g != 1 and n > 0:
			h = n % m
			if h == 0:
				g = 1
				print(c)
				break
			else:
				c += 1
				n -= k
		if g == 0:
			print(-1)


t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	c = 0
	flag = 0
	while n > 0 and flag == 0:
		if n % m == 0:
			if flag == 0:
				print(c)
				flag = 1
		else:
			n = n - k
			c += 1
	if flag == 0:
		print(-1)


t = int(input())
while t != 0:
	t -= 1
	(n, m, k) = [int(x) for x in input().split()]
	r = n % m
	flag = 1
	while n > r:
		if r % k == 0:
			print(r // k)
			flag = 0
			break
		else:
			r += m
	if flag:
		print(-1)


import math
t = int(input())
for tt in range(t):
	(n, m, k) = map(int, input().split())
	aa = n % m
	cc = n // m
	while aa % k != 0 and cc != 0:
		aa += m
		cc -= 1
	if cc == 0:
		print(-1)
	else:
		print(aa // k)


t = int(input())
for x in range(t):
	nm = list(map(int, input().strip().split()))
	n = nm[0]
	m = nm[1]
	k = nm[2]
	if n >= m:
		rem = int(n % m)
		if rem == 0:
			ans = 0
		elif rem % k == 0:
			ans = rem // k
		else:
			while rem % k != 0:
				rem = rem + m
				if rem > n:
					ans = -1
					break
			if rem <= n - m:
				ans = rem // k
			else:
				ans = -1
		print(ans)
	else:
		ans = -1
		print(ans)


t = int(input())
while t > 0:
	(n, m, k) = map(int, input().split())
	equal = int(n / m)
	ans = -1
	for i in range(equal, 0, -1):
		diff = n - m * i
		if diff % k == 0:
			ans = int(diff / k)
			break
	print(ans)
	t -= 1


t = int(input())
for i in range(t):
	(n, m, k) = input().split()
	n = int(n)
	m = int(m)
	k = int(k)
	c = 0
	f = 1
	while n > 0:
		if n % m == 0:
			print(c)
			f = 0
			break
		else:
			n = n - k
			c += 1
			continue
	if f == 1:
		print(-1)


import sys
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]
nb_test = RI()
for _ in range(nb_test):
	(candies, nb_frnd, k) = RMI()
	throws = 0
	thrown = 0
	ans = 0
	while True:
		curr = candies - thrown
		if curr <= 0:
			ans = -1
			break
		if curr % nb_frnd == 0:
			break
		thrown += k
		ans += 1
	print(ans)


T = int(input())
for i in range(T):
	(N, M, K) = map(int, input().split())
	cnt = 0
	while N % M != 0 and N > 0:
		N = N - K
		cnt += 1
	if N <= 0:
		print(-1)
	else:
		print(cnt)


l = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961]
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = n % m
	c = n // m
	while a % k != 0 and c != 0:
		a += m
		c -= 1
	else:
		if c == 0:
			print(-1)
		else:
			print(a // k)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	c = 0
	while True:
		if n < m:
			print(-1)
			break
		r = n // m - c
		if r == 0 and c > 0:
			print(-1)
			break
		r = n - r * m
		if r % k == 0:
			print(int(r / k))
			break
		c += 1


for _ in range(int(input())):
	a = list(map(int, input().split()))
	(count, f) = (0, 0)
	while a[0] >= a[1]:
		if a[0] % a[1] == 0:
			f = 1
			print(count)
			break
		else:
			a[0] -= a[2]
			count += 1
	if f == 0:
		print(-1)


t = int(input())
for _ in range(t):
	[n, m, k] = list(map(int, input().split()))
	q1 = int(n / m)
	q2 = q1 * m
	if (n - q2) % k == 0:
		print(int((n - q2) / k))
	else:
		q = 1
		j = 0
		ts = 0
		while True:
			n = n - q * k
			j += 1
			if n < m:
				break
			if n % m == 0:
				print(j)
				ts = 1
				break
		if ts == 0:
			print(-1)


from sys import stdin
from math import gcd
for _ in range(int(stdin.readline())):
	(n, m, k) = map(int, stdin.readline().split())
	n -= m
	g = gcd(k, m)
	if n >= 0:
		if n % g == 0:
			cond = True
			s = []
			while cond == True and n >= 0:
				if n % m in s:
					cond = False
				else:
					s.append(n % m)
					n -= k
			if 0 in s:
				pos = s.index(0)
				print(pos)
			else:
				print(-1)
		else:
			print(-1)
	else:
		print(-1)


for _ in range(int(input())):
	(n, m, k) = list(map(int, input().split()))
	f = 1
	ans = 0
	while n >= m:
		if n % m == 0:
			f = 0
			print(ans)
			break
		else:
			n = n - k
			ans += 1
	if f == 1:
		print('-1')


import math
t = int(input())
while t:
	t -= 1
	(n, m, k) = [int(x) for x in input().split()]
	if n % m == 0:
		print('0')
		continue
	count = 0
	while n >= m and n % m != 0:
		n -= k
		count += 1
	if n < m:
		print(-1)
	else:
		print(count)


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	if n < m:
		print(-1)
	else:
		throwCandy = n % m
		if throwCandy % k == 0:
			print(throwCandy // k)
		else:
			i = 1
			while i * k < n and (n - i * k) % m != 0:
				i += 1
			if i * k < n and (n - i * k) % m == 0:
				print(i)
			else:
				print(-1)


for _ in range(int(input())):
	(n, m, k) = [int(temp) for temp in input().split()]
	c = 0
	q = n // m
	while q > 0:
		r = n - m * q
		if r % k == 0:
			c += r // k
			print(c)
			break
		q -= 1
	if q <= 0:
		print('-1')


import sys
input()
for numbers in sys.stdin:
	(n, m, k) = map(int, numbers.rstrip().split())
	flag = 0
	if n < m:
		print(-1)
		continue
	left = n // m
	for i in range(left, 0, -1):
		t = n - m * i
		if t % k == 0:
			print(t // k)
			flag = 1
			break
	if not flag:
		print(-1)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	(i, flag) = (0, 0)
	while i * k <= n:
		if (n - i * k) % m == 0:
			flag = 1
			break
		i += 1
	if flag == 1 and (n - i * k) // m > 0:
		print(i)
	else:
		print('-1')


import math
t = int(input())
for _ in range(t):
	(n, m, k) = (int(i) for i in input().split())
	kk = 0
	count = 0
	flag = True
	while True:
		temp = n - kk
		if temp <= 0:
			flag = True
			break
		if temp % m == 0:
			flag = False
			break
		kk += k
		count += 1
	if flag:
		print(-1)
	else:
		print(count)


t = int(input())
while t > 0:
	(n, m, k) = map(int, input().split())
	k1 = k
	i = 1
	flag = 0
	if n % m == 0:
		print('0')
		flag = 1
	if flag == 0:
		uio = 0
		while n % m != 0:
			n = n - k
			if n < m:
				print('-1')
				uio = 1
				break
			i = i + 1
		if uio == 0:
			print(i - 1)
	t = t - 1


x = int(input())
for p in range(x):
	(a, b, c) = map(int, input().split())
	n = 0
	m = 0
	while a >= b:
		if a % b == 0:
			print(n)
			m = 1
			break
		else:
			n += 1
			a -= c
	if m == 0:
		print(-1)


t = int(input())
while t:
	(n, m, k) = map(int, input().split())
	c = -1
	if n < m:
		print(-1)
	else:
		while n >= m:
			n = n - m
			if n % k == 0:
				c = n // k
		print(c)
	t -= 1


def solution(a, b, n):
	i = 0
	while i * a <= n:
		if (n - i * a) % b == 0 and n - i * a != 0:
			return i
		i = i + 1
	return -1
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	if n < m:
		print(-1)
	else:
		print(solution(k, m, n))


for i in range(int(input())):
	(a, b, c) = map(int, input().split())
	k = 1
	if a < b:
		print(-1)
	else:
		for j in range(a // b):
			if (a % b + j * b) % c == 0:
				print((a % b + j * b) // c)
				k = 0
				break
		if k == 1:
			print(-1)


def f():
	t = int(input())
	while t > 0:
		(l, m, n) = map(int, input().split())
		mini = -1
		temp = m
		while l >= m:
			if l % m == 0:
				mini = 0
				break
			if (l - m) % n == 0:
				x = (l - m) // n
				mini = x
			m += temp
		print(mini)
		t -= 1
f()


def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def gcd(n, m):
	if m == 0:
		return n
	if m > n:
		return gcd(m, n)
	return gcd(m, n % m)

def main():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split())
		a = gcd(n, m)
		b = gcd(a, k)
		n = n // b
		m = m // b
		k = k // b
		if gcd(k, m) != 1:
			print(-1)
		else:
			val = n * modInverse(k, m) % m
			if n - k * val > 0:
				print(val)
			else:
				print(-1)
main()


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	import math
	if m > n:
		print(-1)
		continue
	rem = n % m
	while rem % k != 0 and rem < n:
		rem = rem + m
	if rem % k == 0 and rem < n:
		print(rem // k)
	else:
		print(-1)


tc = int(input())
for q in range(tc):
	(n, m, k) = map(int, input().split())
	countre = 0
	(v1, vl) = (0.0, 0)
	j = 0
	while n - k * j > 0:
		vl = (n - k * j) / m
		v1 = (n - k * j) // m
		if vl == v1:
			countre = j
			break
		j += 1
	if j > 0 and countre == 0:
		print(-1)
	else:
		print(countre)


import math

def sol(a, b, c):
	i = 0
	while i * a <= c:
		if (c - a * i) % b == 0 and int((c - a * i) / b) > 0:
			return i
		i += 1
	return -1
for ii in range(int(input())):
	X = input().split()
	N = int(X[0])
	M = int(X[1])
	K = int(X[2])
	ans = sol(K, M, N)
	if ans == -1:
		print(-1)
	else:
		print(ans)


T = int(input())
for _ in range(T):
	(N, M, K) = map(int, input().split())
	cont = 0
	while N % M != 0 and N > M:
		N -= K
		cont += 1
	if N % M == 0 and N >= M:
		print(cont)
	else:
		print(-1)


for T in range(int(input())):
	(n, b, a) = map(int, input().split())
	i = 0
	f = 0
	while i * a <= n:
		if (n - i * a) % b == 0:
			if (n - i * a) // b != 0:
				print(i)
				f = 1
				break
		i = i + 1
	if f == 0:
		print('-1')


for i in range(int(input())):
	(num_can, num_frnd, subs) = map(int, input().split())
	flag = False
	multi_ls = []
	if num_can < num_frnd:
		print(-1)
		flag = True
	else:
		for j in range(num_frnd * (num_can // num_frnd), num_frnd - 1, -num_frnd):
			multi_ls.append(j)
		for k in multi_ls:
			if (num_can - k) % subs == 0:
				print((num_can - k) // subs)
				flag = True
				break
		if flag == False:
			print(-1)