input_num = input()
results = []
inputs = []
for _ in range(int(input_num)):
	i = int(input())
	if i == 1:
		results.append(1)
		inputs.append(0)
	else:
		inputs.append(i)
		results.append(0)
arr = []
for row in range(2, max(inputs) + 1):
	newarr = [0 for _ in range(row-1)]
	newarr[0] = row
	if newarr[0] in inputs:
		for j in range(len(inputs)):
			if inputs[j] == newarr[0]:
				results[j] = row + 1
				inputs[j] = 0
	for a in range(1, len(newarr)):
		if a == len(newarr) - 1:
			newarr[a] = row
		else:
			newarr[a] = arr[a-1] + arr[a]
		if newarr[a] in inputs:
			for j in range(len(inputs)):
				if inputs[j] == newarr[a]:
					results[j] = row + 1
					inputs[j] = 0
	arr = newarr
	if 0 not in results:
		break
for r in results:
	print(r)