Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

You are a poor person in ChocoLand. Here, people eat chocolates daily instead of normal food. There is only one shop near your home; this shop is closed on Sunday, but open on all other days of the week. You may buy at most one box of N chocolates from this shop on each day when it is open.

Currently, it's Monday, and you need to survive for the next S days (including the current day). You have to eat K chocolates everyday (including the current day) to survive. Do note that you are allowed to buy the a chocolate box and eat from it on the same day.

Compute the minimum number of days on which you need to buy from the shop so that you can survive the next S days, or determine that it isn't possible to survive.

------ Input ------ 

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains 3 integers N, K and S denoting the number of chocolates in a box, the number of chocolates you have to eat everyday to survive and the number of days you need to survive.

------ Output ------ 

For each test case, print a single line containing one integer — the minimum number of days on which you need to buy from the shop to survive, or -1 if you will not be able to survive S days.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100$
$1 ≤ K ≤ 100$
$1 ≤ S ≤ 1000$

----- Sample Input 1 ------ 
2
16 2 10
50 48 7
----- Sample Output 1 ------ 
2
-1
----- explanation 1 ------ 
Example case 1: One possible solution is to buy a box on day 1 (Monday); it's sufficient to eat from this box up to day 8 (Monday) inclusive. Now, on day 9 (Tuesday), you buy another box and use the chocolates in it to survive days 9 and 10.
Example case 2: You will not be able to survive even if you buy from the shop everyday except every 7-th day.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Mathematics

Greedy algorithms


Solutions:
for _ in range(int(input())):
	(n, k, s) = map(int, input().split())
	if n < k or (n * 6 < k * 7 and s >= 7) or (n == k and s >= 7):
		print(-1)
		continue
	if k * s % n == 0:
		print(k * s // n)
	else:
		print(k * s // n + 1)


from math import ceil
for t in range(int(input())):
	(n, k, s) = tuple(map(int, input().split()))
	t = ceil(s * k / n)
	print(-1 if t > s - s // 7 else t)


t = int(input())
for i in range(t):
	(n, k, s) = list(map(int, input().split()))
	if n < k:
		print('-1')
		continue
	if s > 6 and 6 * n - 7 * k < 0:
		print('-1')
		continue
	days = s * k // n
	if s * k % n != 0:
		days += 1
	print(days)


import math
tc = int(input())
for _ in range(tc):
	ip = list(map(int, input().split()))
	n = ip[0]
	k = ip[1]
	s = ip[2]
	days = s - s // 7
	res = math.ceil(s * k / n)
	if days < res:
		print(-1)
	else:
		print(res)


import sys
from math import gcd, sqrt, log, ceil, floor
tc = int(input().strip())
for t in range(tc):
	(chocolate, consumption, days) = map(int, input().split())
	if consumption > chocolate:
		print(-1)
		continue
	purchaseReq = ceil(consumption * days / chocolate)
	purchasesPossible = days - days // 7
	if purchaseReq <= purchasesPossible:
		print(purchaseReq)
	else:
		print(-1)


from math import ceil

def soln(n, k, s):
	if n < k:
		return -1
	if n * 6 - k * 7 < 0 and s >= 7:
		return -1
	res = 0
	cur = 0
	for i in range(s):
		if cur < k:
			cur += n
			res += 1
		cur -= k
	return res
for _ in range(int(input())):
	(n, k, s) = map(int, input().split())
	print(soln(n, k, s))


def soln(n, k, s):
	if n < k:
		return -1
	if n * 6 - k * 7 < 0 and s >= 7:
		return -1
	cur = res = 0
	need = k * s
	while cur < need:
		cur += n
		res += 1
	return res
for _ in range(int(input())):
	(n, k, s) = map(int, input().split())
	print(soln(n, k, s))


for _ in range(int(input())):
	(n, s, k) = map(int, input().split())
	if n * 6 >= s * 7:
		p = s * k
		if p % n == 0:
			print(p // n)
		else:
			print(p // n + 1)
	elif n < s:
		print(-1)
	elif n == s and k < 7:
		print(k)
	else:
		print(-1)


t = int(input())
for i in range(t):
	(n, k, s) = map(int, input().split())
	t = k * s
	d = s - s // 7
	if t > n * d or (s >= 7 and (n - k) * 6 < k):
		print('-1')
	else:
		c = t // n
		if t % n != 0:
			c = c + 1
		print(c)


import math
T = int(input())
for i in range(T):
	(N, K, S) = map(int, input().split())
	d = math.ceil(K * S / N)
	if N < K:
		print(-1)
	elif S >= d and 6 * N >= 7 * K:
		print(d)
	elif N == K and S < 7:
		print(S)
	else:
		print(-1)


for x in range(int(input())):
	(n, k, s) = map(int, input().split())
	c = k * s
	day = c // n
	if c % n != 0:
		day += 1
	if day < 7:
		print(day)
	else:
		diff = (n - k) * 6
		if diff >= k:
			print(day)
		else:
			print('-1')


for _ in range(int(input())):
	(n, k, s) = map(int, input().split())
	tot = k * s
	opend = s - s // 7
	if tot > n * opend or (s >= 7 and (n - k) * 6 < k):
		print(-1)
	else:
		ans = tot // n
		if tot % n != 0:
			ans += 1
		print(ans)


for _ in range(int(input())):
	(n, k, s) = map(int, input().split())
	count = 0
	a = n
	b = s
	while s > 0:
		s = s - n // k
		n = a + n % k
		count += 1
	if count > b - b // 7:
		print(-1)
	else:
		print(count)


from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	(n, k, s) = map(int, input().split())
	mn_chok = ceil(k * s / n)
	if s < 7:
		if n >= k:
			print(mn_chok)
		else:
			print(-1)
	elif 7 * k <= 6 * n:
		print(mn_chok)
	else:
		print(-1)


import math
for _ in range(int(input())):
	(n, k, s) = map(int, input().split())
	mn_chok = math.ceil(k * s / n)
	sm = 6 * n - k * 6
	if s < 7:
		print(mn_chok)
	elif sm < k:
		print(-1)
	else:
		print(mn_chok)


import math

def solve():
	days_needed = math.ceil(k * s / n)
	ch_collected_in_6_days = n * 6
	ch_needed_for_7_days = 7 * k
	if n < k:
		print(-1)
	elif n == k and s <= 7:
		if s < 7:
			print(s)
		else:
			print(-1)
	elif n > k and s <= 7:
		if days_needed >= 7:
			print(-1)
		else:
			print(days_needed)
	elif ch_collected_in_6_days < ch_needed_for_7_days:
		print(-1)
	else:
		print(days_needed)
t = int(input())
for _ in range(t):
	(n, k, s) = list(map(int, input().split()))
	solve()


t = int(input())
while t:
	(n, k, s) = map(int, input().split())
	c = k * s
	days = c // n
	if c % n != 0:
		days += 1
	if days < 7:
		print(days)
	else:
		d = (n - k) * 6
		if d >= k:
			print(days)
		else:
			print(-1)
	t -= 1


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def main():
	for _ in tr():
		(n, k, s) = sm()
		week_days = s - s // 7
		buying_days = math.ceil(s * k / n)
		if buying_days > week_days:
			print(-1)
		else:
			print(buying_days)
main()


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def main():
	for _ in tr():
		(n, k, s) = sm()
		if k > n:
			print(-1)
			continue
		count = 0
		days = 0
		total_choco = 0
		possible = True
		for i in range(1, s + 1):
			if i % 7 == 0:
				if total_choco < k:
					if days >= 6:
						possible = False
						break
					else:
						total_choco += n
						count += 1
				days = 0
			elif total_choco < k:
				total_choco += n
				days += 1
				count += 1
			if total_choco >= k:
				total_choco -= k
			else:
				possible = False
				break
		print(count if possible else -1)
main()


try:
	from debug import debug, timer
except ImportError:
	pass
from sys import stdin
input = stdin.readline

def rii():
	return range(int(input().strip()))

def ii():
	return int(input().strip())

def mii():
	return map(int, input().strip().split(' '))

def lmii():
	return list(map(int, input().strip().split(' ')))

def si():
	return str(input().strip())

def getvals():
	while True:
		yield from input().split()

def tri(n):
	return n * (n + 1) // 2

def smallest_first(m, n):
	return (min(m, n), max(m, n))
from math import ceil

def solve(*args):
	(n, k, s) = args
	if n < k:
		return -1
	if n * 6 <= k * 6 and s < 7:
		return ceil(k * s / n)
	if n * 6 < k * 7:
		return -1
	boxes_needed = ceil(k * s / n)
	return boxes_needed

def do_codechef():
	for t in rii():
		(n, k, s) = mii()
		print(solve(n, k, s))
do_codechef()
exit()


import math
try:
	for _ in range(int(input())):
		(n, k, s) = list(map(int, input().split()))
		sundays = s // 7
		weekdays = s - sundays
		required = s * k
		buying_days = math.ceil(required / n)
		if buying_days > weekdays:
			print(-1)
		elif n < k:
			print(-1)
		elif s >= 7 and (n - k) * 6 < k:
			print(-1)
		else:
			print(buying_days)
except:
	pass


t = int(input())
for i in range(t):
	(n, k, s) = map(int, input().split())
	count = s // 7
	m = s - count
	remain = n * m - s * k
	if remain < 0:
		print(-1)
	elif n < k:
		print(-1)
	else:
		res = remain // n
		print(m - res)


import math
T = int(input())
for tj in range(T):
	(N, K, S) = map(int, input().split())
	n_days = math.ceil(S * K / N)
	S -= S // 7
	if n_days > S:
		print(-1)
	else:
		print(n_days)


t = int(input())
for i in range(t):
	(n, k, s) = map(int, input().split())
	weeks = s // 7
	days = s - weeks
	choco = days * n
	chcoreq = k * s
	if chcoreq - choco > 0:
		print(-1)
	else:
		d = chcoreq // n
		if chcoreq % n == 0:
			print(d)
		else:
			print(d + 1)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, k, s) = list(map(int, input().split()))
	left_out = 0
	purchase = 0
	for day in range(1, s + 1):
		if left_out < k and day % 7 != 0:
			purchase += 1
			left_out += n
		elif k < left_out < 2 * k and day % 7 == 6 and (day != s):
			purchase += 1
			left_out += n
		while left_out < k:
			rem_days = day - day // 7 - purchase
			if rem_days > 0:
				purchase += 1
				left_out += n
			else:
				break
		if left_out >= k:
			left_out -= k
		else:
			print(-1)
			break
	else:
		print(purchase)


for _ in range(int(input())):
	(n, k, s) = map(int, input().split())
	(w, d) = (s // 7, s % 7)
	ans = 0
	x = 0
	for _ in range(w):
		temp = k * 7 - x
		if temp % n == 0:
			if temp // n <= 6:
				ans += temp // n
				x = 0
			else:
				ans = -1
				break
		elif temp % n > 0:
			if temp // n <= 5:
				ans += temp // n + 1
				x += n * (temp // n + 1) - 7 * k
			else:
				ans = -1
				break
	if ans >= 0:
		for _ in range(d):
			x -= k
			if x < 0:
				ans += 1
				x += n
				if x < 0:
					ans = -1
					break
	print(ans)


from math import ceil
for _ in range(int(input())):
	(n, k, s) = map(int, input().split())
	a = k * s
	a = ceil(a / n)
	s -= s // 7
	if a <= s:
		print(a)
	else:
		print(-1)


import math
t = int(input())
for i in range(t):
	(n, k, m) = map(int, input().split())
	s = m - m // 7
	c = k * m
	a = n * s
	cs = n / k
	if a >= c:
		ans = int(math.ceil(m / cs))
		print(ans)
	else:
		print(-1)


try:
	import math as ma
	for _ in range(int(input())):
		(n, k, s) = map(int, input().split())
		d = s - s // 7
		req = k * s
		got = n * d
		daysononebox = n / k
		if got >= req:
			print(int(ma.ceil(s / daysononebox)))
		else:
			print(-1)
except EOFError as e:
	pass


import math
for __ in range(int(input())):
	(N, K, S) = map(int, input().split())
	if N < K:
		print(-1)
	elif 7 <= S and (N - K) * 6 < K:
		print(-1)
	else:
		print(math.ceil(K * S / N))


for i in range(int(input())):
	(n, k, s) = map(int, input().split())
	sun = n * (s - s // 7)
	a = k * s
	if a > sun:
		print(-1)
	elif a % n == 0:
		print(a // n)
	else:
		print(a // n + 1)


for _ in range(int(input())):
	(n, k, s) = map(int, input().split())
	sum = n * (s - s // 7)
	a = k * s
	if a > sum:
		print(-1)
	elif a % n == 0:
		print(a // n)
	else:
		print(a // n + 1)


import math
t = int(input())
for i in range(t):
	(n, k, s) = map(int, input().split())
	if n < k:
		print(-1)
	else:
		sun = s // 7
		if s * k / n > s - sun:
			print(-1)
		else:
			ans = math.ceil(s * k / n)
			print(ans)


subtask = int(input())
for _ in range(subtask):
	(N, K, S) = [int(i) for i in input().split()]
	if K > N:
		print(-1)
	else:
		boxes = 0
		day = 0
		chocolates = 0
		requires = S * K
		while chocolates < requires and day <= S:
			if day % 7 != 0:
				boxes += 1
				chocolates += N
			day += 1
		if chocolates >= requires:
			print(boxes)
		else:
			print(-1)


subtask = int(input())
for _ in range(subtask):
	(N, K, S) = [int(i) for i in input().split()]
	if K > N:
		print(-1)
	else:
		b = 0
		d = 0
		c = 0
		R = S * K
		while c < R and d <= S:
			if d % 7 != 0:
				b += 1
				c += N
			d += 1
		if c >= R:
			print(b)
		else:
			print(-1)


for _ in range(int(input())):
	(N, K, S) = [int(s) for s in input().split()]
	Chocolates = 0
	Bought = 0
	Survived = True
	for i in range(1, S + 1):
		BoughtToday = False
		Chocolates -= K
		if Chocolates < 0:
			if i % 7 != 0:
				Chocolates += N
				Bought += 1
				BoughtToday = True
				if Chocolates < 0:
					Survived = False
					break
			else:
				Survived = False
				break
		NextSunday = (i // 7 + 1) * 7
		if not BoughtToday and NextSunday <= S:
			if Chocolates - K < 0:
				Chocolates += N
				Bought += 1
				BoughtToday = True
	if Survived:
		print(Bought)
	else:
		print(-1)


import math
for _ in range(int(input())):
	(n, k, s) = map(int, input().split())
	z = k * s / n
	x = math.ceil(z)
	s = s - s // 7
	if z <= s:
		print(x)
	else:
		print('-1')


T = int(input())
for i in range(T):
	(N, K, S) = map(int, input().split())
	Total = K * S
	Count = 0
	Days = 0
	Flag = False
	for Day in range(1, S + 1):
		if Day % 7 != 0:
			Count += N
			Days += 1
		if Count >= Total:
			Flag = True
			break
	if Flag:
		print(Days)
	else:
		print(-1)


for _ in range(int(input())):
	(n, k, s) = map(int, input().split())
	tot = k * s
	flag = 0
	ans = 0
	c = 0
	for i in range(1, s + 1):
		if i % 7 == 0:
			continue
		else:
			ans = ans + 1
			c = c + n
			if c >= tot:
				flag = 1
				print(ans)
				break
	if flag == 0:
		print(-1)


t = int(input())
for _ in range(t):
	(n, k, s) = [int(x) for x in input().split()]
	sam = k * s
	c = 0
	c1 = 0
	f = 0
	for i in range(1, s + 1):
		if i % 7 != 0:
			c += n
			c1 += 1
		if c >= sam:
			f = 1
			break
	if f == 1:
		print(c1)
	else:
		print(-1)


for _ in range(int(input())):
	(n, k, s) = map(int, input().split())
	t = k * s
	count = 0
	(l, flag) = (0, 0)
	for i in range(1, s + 1):
		if i % 7 != 0:
			l += 1
			count += n
		if count >= t:
			flag = 1
			break
	if flag == 1:
		print(l)
	else:
		print(-1)


import math
for i in range(int(input())):
	(n, k, s) = map(int, input().split())
	d = math.ceil(k * s / n)
	su = d // 7
	if k <= n:
		if d + su > s:
			print(-1)
		else:
			flag = 0
			for j in range(1, su + 1):
				if (7 * j - 1) * n - (7 * j - 1) * k < k:
					flag = 1
					break
			if flag == 1:
				print(-1)
			else:
				print(d)
	else:
		print(-1)


import math
for _ in range(int(input())):
	a = input().split()
	n = int(a[0])
	k = int(a[1])
	s = int(a[2])
	if s < 7:
		if k <= n:
			print(math.ceil(s * k / n))
		else:
			print(-1)
	elif 7 * k <= 6 * n:
		print(math.ceil(s * k / n))
	else:
		print(-1)


for _ in range(int(input())):
	(n, k, d) = list(map(int, input().split()))
	dem = k * d
	ava = n * (d - d // 7)
	day = 0
	if dem <= ava:
		count = 0
		ans = 0
		for i in range(d):
			count += 1
			count %= 7
			if count != 0:
				day += 1
				ans += n
			if ans >= dem:
				break
		print(day)
	else:
		print('-1')


te = int(input())
for _ in range(te):
	(n, k, s) = input().split()
	(n, k, s) = (int(n), int(k), int(s))
	capacity = k * s
	availablity = n * s
	availablity -= n * (s // 7)
	maans = 0
	if capacity <= availablity:
		answer = 0
		counter = 0
		for i in range(s):
			counter += 1
			counter %= 7
			if counter != 0:
				maans += 1
				answer += n
			if answer >= capacity:
				break
		print(maans)
	else:
		print('-1')