10
71
8497
6364
6530
9199
5754
1508
9388
6992
4494
72
8512
8192
8192
9216
8192
2048
9472
8192
4608

for i in range(int(raw_input())):
	n=input()
	for i in range(n,100001):
		if "11" not in str(bin(i)):
			print i
			break