Chef is a very experienced and well-known cook. He has participated in many cooking competitions in the past — so many that he does not even remember them all.
One of these competitions lasted for a certain number of days. The first day of the competition was day $S$ of the week (i.e. Monday, Tuesday etc.) and the last day was day $E$ of the week. Chef remembers that the duration of the competition (the number of days between the first and last day, inclusive) was between $L$ days and $R$ days inclusive. Is it possible to uniquely determine the exact duration of the competition? If so, what is this duration?

-----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 two space-separated strings $S$ and $E$, followed by a space and two space-separated integers $L$ and $R$.

-----Output-----
For each test case, print a single line containing:
- the string "impossible" if there is no duration consistent with all given information
- the string "many" if there is more than one possible duration
- one integer — the duration of the competition, if its duration is unique

-----Constraints-----
- $1 \le T \le 10,000$
- $1 \le L \le R \le 100$
- $S$ is one of the strings "saturday", "sunday", "monday", "tuesday", "wednesday", "thursday" or "friday"
- $E$ is one of the strings "saturday", "sunday", "monday", "tuesday", "wednesday", "thursday" or "friday"

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
3
saturday sunday 2 4
monday wednesday 1 20
saturday sunday 3 5

-----Example Output-----
2
many
impossible

Difficulty: MEDIUM
Tags: Mathematics

Implementation

Starter code:

Solutions:
d = ['saturday', 'sunday', 'monday', 'tuesday', 'wednesday', 'thursday', 'friday']
t = int(input())
for i in range(t):
	(s, e, l, r) = map(str, input().split())
	(l, r) = (int(l), int(r))
	v = (d.index(e) - d.index(s) + 8) % 7
	c = r + 1
	for i in range(l, r + 1):
		if i % 7 == v:
			c = i
			break
	if c > r:
		print('impossible')
	elif c + 7 <= r:
		print('many')
	else:
		print(c)


d = {'monday': 0, 'tuesday': 1, 'wednesday': 2, 'thursday': 3, 'friday': 4, 'saturday': 5, 'sunday': 6}
for _ in range(int(input())):
	(S, E, L, R) = input().split()
	L = int(L)
	R = int(R)
	m_d = (d[E] - d[S] + 8) % 7
	possible = False
	while m_d <= R:
		if m_d >= L:
			possible = True
			if m_d + 7 <= R:
				print('many')
			else:
				print(m_d)
			break
		m_d += 7
	if not possible:
		print('impossible')


import math
for _ in range(int(input())):
	(a, b, n, m) = input().split()
	n = int(n)
	m = int(m)
	days = ['monday', 'tuesday', 'wednesday', 'thursday', 'friday', 'saturday', 'sunday']
	duration_days = (days.index(b) - days.index(a) + 7) % 7 + 1
	d = []
	for i in range(duration_days, m + 1, 7):
		d.append(i)
	c = 0
	for i in d:
		if i >= n and i <= m:
			c += 1
			duration_days = i
	if c > 1:
		print('many')
	elif c == 1:
		print(duration_days)
	else:
		print('impossible')


t = int(input())
for _ in range(t):
	(sd, ed, l, r) = input().split(' ')
	(l, r) = (int(l), int(r))
	d = {'saturday': 0, 'sunday': 1, 'monday': 2, 'tuesday': 3, 'wednesday': 4, 'thursday': 5, 'friday': 6}
	if d[ed] >= d[sd]:
		x = d[ed] - d[sd] + 1
	else:
		x = d[ed] - d[sd] + 8
	temp = 0
	count = 0
	while x <= r:
		if l <= x <= r:
			temp = x
			count += 1
		x += 7
	if count == 0:
		print('impossible')
	elif count == 1:
		print(temp)
	else:
		print('many')


T = int(input())
dic = {'monday': 1, 'tuesday': 2, 'wednesday': 3, 'thursday': 4, 'friday': 5, 'saturday': 6, 'sunday': 7}
for ti in range(T):
	(s, e, l, r) = input().split()
	lint = int(l)
	div = lint // 7
	rint = int(r)
	difdays = (dic[e] - dic[s]) % 7 + 1
	if difdays + 7 * div >= lint and difdays + 7 * div <= rint or (difdays + 7 * (div - 1) >= lint and difdays + 7 * (div - 1) <= rint) or (difdays + 7 * (div + 1) >= lint and difdays + 7 * (div + 1) <= rint):
		if (difdays + 7 * div >= lint and difdays + 7 * div <= rint) and (difdays + 7 * (div + 1) >= lint and difdays + 7 * (div + 1) <= rint) or ((difdays + 7 * (div + 1) >= lint and difdays + 7 * (div + 1) <= rint) and (difdays + 7 * (div + 2) >= lint and difdays + 7 * (div + 2) <= rint)) or ((difdays + 7 * div >= lint and difdays + 7 * div <= rint) and (difdays + 7 * (div - 1) >= lint and difdays + 7 * (div - 1) <= rint)):
			print('many')
		elif difdays + 7 * div >= lint and difdays + 7 * div <= rint:
			print(difdays + 7 * div)
		elif (difdays + 7 * (div + 1) >= lint and difdays + 7 * (div + 1)) <= rint:
			print(difdays + 7 * (div + 1))
		elif difdays + 7 * (div - 1) >= lint and difdays + 7 * (div - 1) <= rint:
			print(difdays + 7 * (div - 1))
	else:
		print('impossible')


lst = ['sunday', 'monday', 'tuesday', 'wednesday', 'thursday', 'friday', 'saturday']
for _ in range(int(input())):
	(s, e, l, r) = input().split()
	(s, e) = (lst.index(s), lst.index(e))
	(l, r) = map(int, [l, r])
	if e < s:
		e += 7
	d = e - s + 1
	while d < l:
		d += 7
	if d <= r and d <= r - 7:
		print('many')
	elif d <= r:
		print(d)
	else:
		print('impossible')


t = int(input())
dic = {'sunday': 2, 'monday': 3, 'tuesday': 4, 'wednesday': 5, 'thursday': 6, 'friday': 7, 'saturday': 1}
for i in range(t):
	(ws, we, l, r) = tuple(input().split())
	l = int(l)
	r = int(r)
	rem = (7 - dic[ws] + 1 + dic[we]) % 7
	mrem = l % 7
	if mrem <= rem:
		l += rem - mrem
	else:
		l += 7 - mrem + rem
	if l <= r:
		if l + 7 <= r:
			print('many')
		else:
			print(l)
	else:
		print('impossible')


def val(s):
	if s == 'sunday':
		return 1
	elif s == 'monday':
		return 2
	elif s == 'tuesday':
		return 3
	elif s == 'wednesday':
		return 4
	elif s == 'thursday':
		return 5
	elif s == 'friday':
		return 6
	else:
		return 7
t = int(input())
for _ in range(t):
	(sd, ed, l, r) = map(str, input().split())
	(l, r) = (int(l), int(r))
	vl = val(sd)
	vr = val(ed)
	if vr >= vl:
		k = vr - vl + 1
	else:
		k = vr - vl + 8
	count = 0
	ans = None
	while k <= r:
		if k >= l and k <= r:
			count += 1
			ans = k
		k = k + 7
	if count == 0:
		print('impossible')
	elif count == 1:
		print(ans)
	else:
		print('many')


def day(k):
	return [0, 'sunday', 'monday', 'tuesday', 'wednesday', 'thursday', 'friday', 'saturday'].index(k)
for x in range(int(input())):
	(sd, ed, l, r) = input().split(' ')
	(l, r) = (int(l), int(r))
	d = {'saturday': 0, 'sunday': 1, 'monday': 2, 'tuesday': 3, 'wednesday': 4, 'thursday': 5, 'friday': 6}
	if d[ed] >= d[sd]:
		x = d[ed] - d[sd] + 1
	else:
		x = d[ed] - d[sd] + 8
	temp = 0
	count = 0
	while x <= r:
		if l <= x <= r:
			temp = x
			count += 1
		x += 7
	if count == 0:
		print('impossible')
	elif count == 1:
		print(temp)
	else:
		print('many')


tests = int(input())
arr = ['saturday', 'sunday', 'monday', 'tuesday', 'wednesday', 'thursday', 'friday']
for i in range(tests):
	(start, end, minimum, maximum) = input().split()
	start_index = arr.index(start)
	end_index = arr.index(end)
	gap = (end_index - start_index) % 7
	gap += 1
	ans = 'impossible'
	minimum = int(minimum)
	maximum = int(maximum)
	factor = minimum // 7
	days_start = gap
	if days_start < minimum:
		days_start = gap + factor * 7
	if days_start < minimum:
		days_start += 7
	elif days_start > maximum:
		days_start -= 7
	if minimum <= days_start <= maximum:
		if minimum <= days_start + 7 <= maximum or minimum <= days_start - 7 <= maximum:
			ans = 'many'
		else:
			ans = days_start
	print(ans)


days = {'saturday': 1, 'sunday': 2, 'monday': 3, 'tuesday': 4, 'wednesday': 5, 'thursday': 6, 'friday': 7}
for _ in range(int(input())):
	(a, b, c, d) = input().split()
	c = int(c)
	d = int(d)
	x = days[a]
	y = days[b]
	if x <= y:
		t = y - x + 1
	else:
		t = y + 7 - x + 1
	ans = []
	for _ in range(20):
		if t in range(c, d + 1):
			ans.append(t)
		t = t + 7
	if len(ans) > 1:
		print('many')
	elif len(ans) == 0:
		print('impossible')
	else:
		print(ans[0])


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()]
days = ['saturday', 'sunday', 'monday', 'tuesday', 'wednesday', 'thursday', 'friday']
for _ in range(RI()):
	(sday, eday, l, r) = RWI()
	(l, r) = (int(l), int(r))
	interval = (days.index(eday) - days.index(sday) + 8) % 7
	cnts = 0
	while interval <= r:
		if l <= interval <= r:
			cnts += 1
		interval += 7
	ans = 'impossible'
	if cnts == 1:
		ans = interval - 7
	elif cnts > 1:
		ans = 'many'
	print(ans)


h = 1
kk = 0
f = {'monday': 0, 'tuesday': 1, 'wednesday': 2, 'thursday': 3, 'friday': 4, 'saturday': 5, 'sunday': 6}
for _ in range(int(input())):
	(a, b, c, d) = input().split()
	c = int(c)
	d = int(d)
	ff = (f[b] - f[a] + 8) % 7
	possible = False
	while ff <= d:
		if ff >= c:
			possible = True
			if ff + 7 <= d:
				print('many')
			else:
				print(ff)
			break
		ff += 7
	if not possible:
		print('impossible')


def a(b):
	if b == 'monday':
		return 0
	elif b == 'tuesday':
		return 1
	elif b == 'thursday':
		return 3
	elif b == 'friday':
		return 4
	elif b == 'saturday':
		return 5
	elif b == 'sunday':
		return 6
	else:
		return 2
for _ in range(int(input())):
	(c, d, e, f) = input().split()
	(c, d) = (a(c), a(d))
	(e, f) = (int(e), int(f))
	if c >= d:
		d += 7
	c = d - c + 1
	j = 0
	for i in range(e, f + 1):
		if (i - c) % 7 == 0:
			if j != 0:
				j = -1
				break
			else:
				j = i
	if j == 0:
		print('impossible')
	elif j == -1:
		print('many')
	else:
		print(j)


t = int(input())
for _ in range(t):
	(a, b, p, r) = map(str, input().split())
	(p, r) = (int(p), int(r))
	l = []
	k = 0
	l1 = ['saturday', 'sunday', 'monday', 'tuesday', 'wednesday', 'thursday', 'friday']
	if abs(l1.index(a) > l1.index(b)):
		d = 7 - abs(l1.index(a) - l1.index(b)) + 1
	else:
		d = abs(l1.index(a) - l1.index(b)) + 1
	for i in range(20):
		if d in range(p, r + 1):
			l.append(d)
		d = d + 7
	if len(l) == 1:
		print(l[0])
	elif len(l) > 1:
		print('many')
	elif len(l) == 0:
		print('impossible')


days = ['saturday', 'sunday', 'monday', 'tuesday', 'wednesday', 'thursday', 'friday']
for i in range(int(input())):
	(s, e, l, r) = map(str, input().split())
	(l, r) = (int(l), int(r))
	value = (days.index(e) - days.index(s) + 8) % 7
	count = r + 1
	for i in range(l, r + 1):
		if i % 7 == value:
			count = i
			break
	if count > r:
		print('impossible')
	elif count + 7 <= r:
		print('many')
	else:
		print(count)


for i in range(int(input())):
	days = list(input().split())
	notes = {'saturday': 1, 'sunday': 2, 'monday': 3, 'tuesday': 4, 'wednesday': 5, 'thursday': 6, 'friday': 7}
	t_days = 0
	z1 = days[0]
	z2 = days[1]
	x = notes[str(z1)]
	y = notes[str(z2)]
	if x <= y:
		t_days = y - x + 1
	else:
		t_days = y + 7 - x + 1
	c = 0
	file = []
	for _ in range(17):
		if t_days in range(int(days[2]), int(days[3]) + 1):
			c += 1
			file.append(t_days)
		if c == 2:
			print('many')
			break
		if t_days >= int(days[3]) and c == 1:
			print(file[0])
			break
		elif t_days >= int(days[3]) and c == 0:
			print('impossible')
			break
		t_days += 7


import sys
input = sys.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())
days = ['monday', 'tuesday', 'wednesday', 'thursday', 'friday', 'saturday', 'sunday']

def solve(line):
	(s, e, l, r) = line.split(' ')
	(l, r) = (int(l), int(r))
	gap = (days.index(e) - days.index(s) + 1) % 7
	for i in range(l, min(r, l + 7) + 1):
		if i % 7 == gap:
			if i + 7 <= r:
				return 'many'
			else:
				return i
	return 'impossible'

def do_codechef():
	for t in rii():
		line = si()
		print(solve(line))
do_codechef()
exit()


repeat = int(input())
week = ['sunday', 'monday', 'tuesday', 'wednesday', 'thursday', 'friday', 'saturday']
while repeat > 0:
	count = 0
	length = 1
	inputs = input().split(' ')
	(start, end) = (inputs[0], inputs[1])
	index = week.index(start)
	while week[index] != end:
		length += 1
		index = (index + 1) % 7
	power = 0
	while length + 7 * power <= int(inputs[3]):
		if length + power * 7 <= int(inputs[3]) and length + power * 7 >= int(inputs[2]):
			count += 1
			result = length + 7 * power
		power += 1
	if count == 0:
		print('impossible')
	elif count == 1:
		print(result)
	else:
		print('many')
	repeat -= 1


dictionary = {'saturday': 1, 'sunday': 2, 'monday': 3, 'tuesday': 4, 'wednesday': 5, 'thursday': 6, 'friday': 7}
for _ in range(int(input())):
	(S, E, L, R) = map(str, input().split())
	L = int(L)
	R = int(R)
	array = [i for i in range(L, R + 1)]
	res = 0
	ans = 0
	for i in range(len(array)):
		k = 1
		count = dictionary[S]
		for j in range(array[i] - 1):
			if count == 7:
				count = 1
				continue
			count += 1
		if count == dictionary[E]:
			res += 1
			ans = array[i]
		if res > 1:
			ans = 'many'
			break
	else:
		if res == 0:
			ans = 'impossible'
	print(ans)


t = int(input())
week = ['sunday', 'monday', 'tuesday', 'wednesday', 'thursday', 'friday', 'saturday']
for _ in range(t):
	(s, e, l, r) = [x for x in input().split()]
	l = int(l)
	r = int(r)
	a = week.index(s)
	b = week.index(e)
	c = 1
	while a != b:
		c += 1
		a += 1
		a = a % 7
	sam = 0
	while c <= r:
		if c >= l and c <= r:
			sam += 1
		c += 7
	c -= 7
	if sam == 0:
		print('impossible')
	elif sam == 1:
		print(c)
	else:
		print('many')


for _ in range(int(input())):
	SELR = list(map(str, input().split(' ')))
	(Days, Times, Event, Ans) = (['monday', 'tuesday', 'wednesday', 'thursday', 'friday', 'saturday', 'sunday'], 0, 0, 0)
	Event = (Days.index(SELR[1]) - Days.index(SELR[0]) + 8) % 7
	for i in range(int(SELR[2]), int(SELR[3]) + 1):
		if i % 7 == Event:
			Times += 1
			Ans = i
	if Times > 1:
		print('many')
	elif Times == 0:
		print('impossible')
	elif Times == 1:
		print(Ans)


t = int(input())
while t > 0:
	t -= 1
	n = input().split()
	(r, c) = (int(n[2]), int(n[3]))
	d = {'monday': 2, 'tuesday': 3, 'wednesday': 4, 'thursday': 5, 'friday': 6, 'saturday': 7, 'sunday': 1}
	n1 = d[n[0]]
	n2 = d[n[1]]
	k = n2 - n1 + 1
	while k < r:
		k = k + 7
	if k > c:
		print('impossible')
	elif k + 7 > c:
		print(k)
	else:
		print('many')


xd = {'monday': 1, 'tuesday': 2, 'wednesday': 3, 'thursday': 4, 'friday': 5, 'saturday': 6, 'sunday': 0}
for _ in range(int(input())):
	(s, e, l, r) = input().split()
	(l, r) = (int(l), int(r))
	(s, e) = (xd[s], xd[e])
	if s <= e:
		d = e - s + 1
	elif s > e:
		d = e - s + 8
	rr = d + 7 * ((r - d) // 7)
	if rr < l:
		print('impossible')
	elif rr - 7 >= l:
		print('many')
	elif rr - 7 < l:
		print(rr)


d = {'sunday': 1, 'monday': 2, 'tuesday': 3, 'wednesday': 4, 'thursday': 5, 'friday': 6, 'saturday': 7}
for _ in range(int(input())):
	(start, end, l, r) = map(str, input().split())
	(l, r) = (int(l), int(r))
	if d[end] >= d[start]:
		k = d[end] - d[start] + 1
	else:
		k = d[end] - d[start] + 8
	count = 0
	ans = None
	while k <= r:
		if k >= l and k <= r:
			ans = k
			count += 1
		k += 7
	if count == 0:
		print('impossible')
	elif count == 1:
		print(ans)
	else:
		print('many')


days = ['monday', 'tuesday', 'wednesday', 'thursday', 'friday', 'saturday', 'sunday']
for _ in range(int(input())):
	(s, e, l, r) = map(str, input().split())
	s_ind = days.index(s)
	e_ind = days.index(e)
	p = (e_ind - s_ind + 7) % 7 + 1
	l = int(l)
	r = int(r)
	cnt = 0
	while p <= r:
		if p >= l and p <= r:
			cnt += 1
		p += 7
	if cnt == 1:
		print(p - 7)
	elif cnt == 0:
		print('impossible')
	elif cnt > 1:
		print('many')