T = int(raw_input().strip())
for case in range(T):
	y= map(int, raw_input().strip().split())
	d=1
	m=5
	w= (d+2*m+3*(m+1)/5+y[0]+y[0]/4-y[0]/100+y[0]/400) % 7
	if w==0:
		print 9
	elif w==6:
		print 6
	elif w==1:
		print 6
	else:
		print 5