Alice likes all the numbers which are divisible by A. Bob does not like the numbers which are divisible by B and likes all the remaining numbers. Determine the smallest number greater than or equal to N which is liked by both Alice and Bob. Output -1 if no such number exists.

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains three space-separated integers A, B and N — the parameters mentioned in the problem statment.

------ Output Format ------ 

For each test case, output the smallest number ≥ N which is divisible by A and is not divisible by B. Output -1 if no such number exists.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ A, B, N ≤ 10^{9}$

----- Sample Input 1 ------ 
3
5 2 11
4 3 24
7 7 100

----- Sample Output 1 ------ 
15
28
-1

----- explanation 1 ------ 
Test case $1$: $15$ is the smallest number $≥$ $11$ which is divisible by $5$ and is not divisible by $2$.

Test case $2$: $28$ is the smallest number $≥$ $24$ which is divisible by $4$ and is not divisible by $3$.

Test case $3$: There does not exist any number which is divisible by $A = 7$ and is not divisible by $B = 7$.

Source: codechef | Difficulty: EASY
Tags: Mathematics


Solutions:
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a % b == 0:
		print(-1)
	elif n % a == 0 and n % b == 0:
		print(n + a)
	elif n % a == 0:
		print(n)
	else:
		n -= n % a
		if (n + a) % a == 0 and (n + a) % b != 0:
			print(n + a)
		else:
			print(n + 2 * a)


for i in range(int(input())):
	(A, B, N) = map(int, input().split())
	j = N - N % A
	if A % B == 0:
		print(-1)
	else:
		if N % A != 0:
			j += A
		if j % B == 0:
			j += A
		print(j)


T = int(input())
for _ in range(T):
	(A, B, N) = map(int, input().split())
	j = N - N % A
	if A % B == 0:
		print(-1)
	else:
		if N % A != 0:
			j += A
		if j % B == 0:
			j += A
		print(j)


testcases = int(input())
while testcases > 0:
	(A, B, C) = map(int, input().split())
	n = C - C % A
	if A % B == 0:
		print(-1)
	else:
		if C % A != 0:
			n += A
		if n % B == 0:
			n += A
		print(n)
	testcases -= 1


import math
for _ in range(int(input())):
	(A, B, N) = map(int, input().split())
	N = math.ceil(N / A) * A
	if A % B == 0:
		print('-1')
	elif N % B == 0:
		print(N + A)
	else:
		print(N)


def ceil(k):
	if k > int(k):
		return int(k) + 1
	else:
		return int(k)
T = int(input())
for _ in range(T):
	(a, b, n) = list(map(int, input().split()))
	n = a * ceil(n / a)
	if n % b == 0:
		n = n + a
	if n % b == 0:
		print(-1)
	else:
		print(n)


for _ in range(int(input())):
	(A, B, N) = map(int, input().split())
	if A % B == 0:
		print(-1)
	else:
		R = N - N % A
		if N % A != 0:
			R = R + A
		if R % B == 0:
			R = R + A
		print(R)


for i in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a % b == 0:
		print(-1)
	else:
		r = n - n % a
		if n % a != 0:
			r = r + a
		if r % b == 0:
			r = r + a
		print(r)


for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a % b == 0:
		print('-1')
	else:
		ans = n - n % a
		if n % a != 0:
			ans += a
		if ans % b == 0:
			ans += a
		print(ans)


for _ in range(int(input())):
	x = 0
	(a, b, n) = map(int, input().split())
	if a % b == 0:
		print(-1)
		continue
	x = n
	if x % a != 0:
		x = n + a - x % a
	while not (x % a == 0 and x % b != 0):
		x += a
	print(x)


t = int(input())
for _ in range(t):
	(a, b, n) = map(int, input().split())
	if a % b == 0:
		print(-1)
	else:
		x = n - n % a
		if n % a != 0:
			x += a
		if x % b == 0:
			x += a
		print(x)


t = int(input())
import math
for i in range(t):
	a_b_n = input().split(' ')
	(a, b, n) = (int(a_b_n[0]), int(a_b_n[1]), int(a_b_n[2]))
	if math.gcd(a, b) == b:
		print(-1)
	elif n % a == 0 and n % b != 0:
		print(n)
	elif n % a != 0:
		if (n + (a - n % a)) % b != 0:
			print(n + (a - n % a))
		else:
			print(n + (a - n % a) + a)
	elif n % a == 0 and n % b == 0:
		print(n + a)


import math as m
for t in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a % b == 0:
		print(-1)
	else:
		x = a * m.ceil(n / a)
		if x % b == 0:
			print(x + a)
		else:
			print(x)


t = int(input())
for tc in range(t):
	(a, b, n) = map(int, input().split())
	j = n - n % a
	if a % b == 0:
		print(-1)
	else:
		if n % a != 0:
			j += a
		if j % b == 0:
			j += a
		print(j)


import math as m
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a % b == 0:
		print(-1)
	else:
		i = int(m.ceil(n / a))
		while True:
			if a * i >= n and a * i % b != 0:
				break
			else:
				i += 1
		print(i * a)


x = int(input())
prt = []
for jj in range(0, x):
	rt = str(input())
	hk = rt.split(' ')
	pr = []
	for nn in hk:
		pr.append(int(nn))
	prt.append(pr)
for jkr in prt:
	if jkr[0] == jkr[1]:
		print(-1)
	elif jkr[0] % jkr[1] == 0:
		print(-1)
	elif jkr[2] % jkr[0] == 0 and jkr[2] % jkr[1] != 0:
		print(jkr[2])
	elif jkr[2] % jkr[0] == 0 and jkr[2] % jkr[1] == 0:
		print(jkr[2] + jkr[0])
	else:
		uml = jkr[2] - jkr[2] % jkr[0]
		uml += jkr[0]
		while True:
			if uml % jkr[1] != 0:
				print(uml)
				break
			uml += jkr[0]


t = int(input())
for i in range(t):
	(a, b, n) = map(int, input().split())
	if a % b == 0:
		print('-1')
	else:
		ans = n - n % a
		if n % a != 0:
			ans += a
		if ans % b == 0:
			ans += a
		print(ans)


from sys import stdin
from math import ceil
for _ in range(int(stdin.readline())):
	(a, b, n) = map(int, stdin.readline().split())
	if a % b == 0:
		print(-1)
	else:
		t = ceil(n / a)
		print(t * a if t * a % b != 0 else (t + 1) * a)


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


for tc in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a % b == 0:
		print('-1')
	else:
		if n % a == 0:
			num = n
		else:
			num = a * (n // a + 1)
		while num % b == 0:
			num += a
		print(num)


def solve(a, b, n):
	if a % b == 0:
		return -1
	res = n - n % a
	if n % a != 0:
		res += a
	if res % b == 0:
		res += a
	return res
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	print(solve(a, b, n))


for u in range(int(input())):
	l = [int(i) for i in input().split()]
	(a, b, n) = l
	if a % b == 0 or b == 1:
		print(-1)
	else:
		x = n // a * a
		if n % b != 0 and x >= n:
			print(x)
		elif (x + a) % b != 0:
			print(x + a)
		else:
			print(x + 2 * a)


for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	x = 0
	if a % b == 0:
		x = -1
	else:
		x = max(n, a)
		if x % a != 0:
			x -= x % a - a
	for i in range(x, x + a * 10, a):
		if i % b != 0:
			x = i
			break
	print(x)


from math import ceil
inps = int(input())
for i in range(inps):
	(A, B, N) = input().split(' ')
	(A, B, N) = (int(A), int(B), int(N))
	if A % B == 0 or A == B:
		print(-1)
	else:
		N = ceil(N / A) * A
		while N % A != 0 or N % B == 0:
			N += A
		print(N)


import math
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a % b:
		c = math.ceil(n / a) * a
		if c % b:
			print(c)
		else:
			print(c + a)
	else:
		print(-1)


import math

def main():
	T = int(input())
	for _ in range(T):
		(A, B, N) = map(int, input().split())
		if A % B == 0:
			print('-1')
		else:
			N = math.ceil(N / A) * A
			while 1:
				if N % A == 0 and N % B != 0:
					print(N)
					break
				N += A
main()


import math
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a % b == 0:
		print(-1)
	else:
		while 1:
			n = math.ceil(n / a) * a
			if n % a == 0 and n % b != 0:
				res = n
				break
			else:
				n += a
		print(res)


for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a % b == 0:
		print(-1)
	else:
		flag = True
		x = n // a * a
		if x % b != 0 and x >= n:
			print(x)
		else:
			while flag:
				x += a
				if x % b != 0:
					flag = False
			print(x)


import math
for _ in range(int(input())):
	(x, y, z) = map(int, input().split())
	c = math.ceil(z / x)
	if x % y == 0:
		print(-1)
	elif x * c % y != 0:
		print(x * c)
	else:
		print(x * (c + 1))


import math
for i in range(int(input())):
	(a, b, n) = input().split()
	(a, b, n) = (int(a), int(b), int(n))
	if a % b == 0:
		print(-1)
	else:
		x = a * math.ceil(n / a)
		if x % b != 0:
			print(x)
		else:
			print(x + a)


t = int(input())
for i in range(t):
	(a, b, n) = map(int, input().split())
	k = 1
	if a % b == 0:
		print(-1)
	else:
		x = n // a * a
		if x % b != 0 and x >= n:
			print(x)
		else:
			while k == 1:
				x = x + a
				if x % b != 0:
					k = 0
			print(x)


for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a % b == 0:
		print(-1)
	else:
		ns = -(-n // a) * a
		if ns % b != 0:
			print(ns)
		else:
			while ns % b == 0:
				ns += a
			print(ns)


g = int(input())
for i in range(g):
	(A, B, C) = map(int, input().split())
	if A % B == 0:
		print(-1)
	else:
		if C % A != 0:
			C = (C // A + 1) * A
		while C % B == 0:
			C = C + A
		print(C)


import math
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a % b == 0:
		print(-1)
	elif n % a == 0 and n % b != 0:
		print(n)
	else:
		c = a * (n // a + 1)
		if c % b == 0:
			print(c + a)
		else:
			print(c)


T = int(input())
for t in range(T):
	(a, b, n) = map(int, input().split())
	if a % b == 0:
		print('-1')
	elif n % a == 0 and n % b != 0:
		print(n)
	else:
		x = a * (n // a + 1)
		if x % b == 0:
			print(x + a)
		else:
			print(x)


from math import gcd, ceil
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if gcd(a, b) == b:
		print(-1)
	else:
		starts = ceil(n / a) * a
		while True:
			if starts % a == 0 and starts % b != 0:
				print(starts)
				break
			starts += a


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


T = int(input())
for i in range(T):
	(a, b, c) = map(int, input().split())
	if a == b or a % b == 0:
		print(-1)
	elif c % a == 0 and c % b != 0:
		print(c)
	else:
		d = a - c % a
		c += d
		while c % b == 0:
			c += a
		print(c)


t = int(input())
while t != 0:
	(n, m, p) = map(int, input().split())
	if n % m == 0:
		print(-1)
	else:
		while True:
			if p % n == 0 and p % m != 0:
				print(p)
				break
			else:
				p += n - p % n
	t -= 1


import math
for t in range(int(input())):
	(a, b, n) = map(int, input().split())
	sum = 0
	if a % b == 0:
		print('-1')
	elif n % a == 0 and n % b != 0:
		print(n)
	else:
		r = math.ceil(n / a)
		r = r * a
		while 1:
			if r % a == 0 and r % b != 0:
				print(r)
				break
			else:
				r = r + a


for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a % b == 0:
		print(-1)
	elif n % a == 0 and n % b != 0:
		print(n)
	else:
		r = n % a
		x = n + a - r
		while 1:
			if x % b != 0:
				break
			x += a
		print(x)


t = int(input())
while t:
	(a, b, n) = map(int, input().split())
	if a % b == 0:
		print('-1')
	else:
		while 1:
			if n % a == 0 and n % b != 0:
				print(n)
				break
			else:
				n += a - n % a
	t -= 1