You are a person who is always fond of eating candies. Your friend gave you a candy of length N, to eat during the break period of your school.

You start eating this candy from one of the ends. But as it is not your candy, your friend told you to eat exactly K unit length of candy during each bite. You will stop eating if the candy's length becomes 0. This means that you have eaten the entire candy. 

If at some point of time, the candy's length is positive, but less than K, you *cannot* take a bite thereafter.

Can you eat the complete candy? If yes, print the number bites it will take, else print -1.

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

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains of two spaced integers N, K.

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

For each testcase, print the minimum number of bites you need to eat the complete candy. Print -1 if it is
not possible to do so.

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

$1 ≤ T ≤ 10^{5}$
$0 ≤ N ≤ 10^{6}$
$1 ≤ K ≤ 10^{6}$

----- Sample Input 1 ------ 
3
3 1
3 2
0 3

----- Sample Output 1 ------ 
3
-1
0

----- explanation 1 ------ 
Test case 1:
When you eat your first bite of length $1$, the length of the candy will become $2$. After the second bite, the candy's length will be $1$ and finally after the third bite, candy's length will be $0$, and hence you eat the entire candy!

Test case 2:
After the first bite, candy's length will become $1$. You cannot go for the second bite as candy's length is positive and less than $2$.

Test case 3: 
Candy's length is already $0$, hence it can be said that you have eaten the entire candy!

Source: codechef | Difficulty: EASY
Tags: Number theory

Mathematics


Solutions:
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	if n == 0:
		print(0)
	elif n % k != 0:
		print(-1)
	else:
		print(n // k)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	if n % k == 0:
		print(int(n / k))
	else:
		print('-1')


for i in range(int(input())):
	(N, k) = map(int, input().split())
	if N % k == 0:
		print(N // k)
	else:
		print('-1')


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


for i in range(int(input())):
	(m, n) = map(int, input().split())
	bites = m % n
	if bites == 0:
		print(m // n)
	else:
		print(-1)


T = int(input())
for o in range(T):
	(N, K) = map(int, input().split())
	if N % K == 0:
		print(N // K)
	else:
		print(-1)


T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	m = n // k
	if n == 0:
		print(0)
	elif n % k:
		print(-1)
	else:
		print(m)


for i in range(int(input())):
	x = input()
	y = x.split(' ')
	a = int(y[0])
	b = int(y[1])
	if a % b == 0:
		print(a // b)
	else:
		print(-1)


t = int(input())
for i in range(t):
	(N, K) = map(int, input().split())
	if N % K == 0:
		print(N // K)
	else:
		print(-1)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	if x % y == 0:
		print(x // y)
	else:
		print(-1)


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


for i in range(int(input())):
	(n, k) = map(int, input().split())
	c = -1
	if n % k == 0:
		c = n // k
	print(c)


for case in range(int(input())):
	(n, k) = map(int, input().split())
	print(int(n // k)) if n % k == 0 else print(-1)


t = int(input())
for t in range(t):
	lis = list(map(int, input().split()))
	(a, b) = lis
	if a % b == 0:
		print(int(a / b))
	else:
		print('-1')


t = int(input())
while t > 0:
	(n, k) = [int(x) for x in input().split()]
	bites = 0
	if n % k == 0:
		bites = n / k
	else:
		bites = -1
	print(int(bites))
	t -= 1


n = int(input())
for i in range(n):
	(p, q) = map(int, input().split())
	if p % q == 0:
		print(p // q)
	else:
		print(-1)


n = int(input())
for i in range(n):
	a = list(map(int, input().split()))
	if a[0] % a[1] == 0:
		print(int(a[0] / a[1]))
	else:
		print(-1)


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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	z = int(n / k)
	if n % k == 0:
		print(z)
	else:
		print('-1')


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	print(N // K) if N % K == 0 else print(-1)


for i in range(int(input())):
	(total, specific) = map(int, input().split())
	if total % specific == 0:
		print(total // specific)
	else:
		print(-1)


try:
	t = int(input())
	for r in range(t):
		(n, k) = map(int, input().split())
		if n % k == 0:
			print(n // k)
		else:
			print(-1)
except:
	pass


a = int(input())
for i in range(a):
	(n, k) = list(map(int, input().split()))
	if n % k == 0:
		print(int(n / k))
	elif n % k != 0:
		print(-1)
	elif n == 0:
		print(0)


t = int(input())
while t != 0:
	(n, k) = list(map(int, input().split()))
	if n % k == 0:
		print(n // k)
	else:
		print('-1')
	t = t - 1