Bittijono

### BITTIJONO (dt2k18) ###

# ok i know that's not a good answer. But it wurkz. And probably gives a few points

# lol main again :D
def main(n):
	# just a random (mod'd, n-2) Fibonacci series to ease computation ;)
	fib = [1, 3, 6, 11, 19, 32, 53, 87, 142, 231, 375, 608, 985, 1595, 2582, 4179, 6763, 10944, 
			17709, 28655, 46366, 75023, 121391, 196416, 317809, 514227, 832038, 1346267]

	# some serious iterating here
	i = iter(fib)
	t = 1

	# finding a lower limit
	while True:
		if t > n:
			break

		elif t == n:
			# wow we haz an special case here
			pass

		t = i.__next__()


	# lets start the raw, computionally intensive brainfuck (i mean that language)
	# this looks like it could be done with a C for
	i = t
	while True:
		b = bin(i)[2:]
		res = tester(b)
		if res == n:
			return b
		i += 1

### TEST AREA BEGINS ###

# this function tests the string (and decrements it by 1 as "" isnt consireded as a subseq by spec)
# dont even try to understand this, me does not understand it either (or so i say ( ͡° ͜ʖ ͡°))
def tester(a, verbosity=0):
	# technical styff
	n = len(a)
	last = {}
	dp = {}
	dp[-1] = 1 # we haz to haz this start value
	# O(n) iteration over errytin'
	for i in range(n):
		if verbosity > 2: print("\nCHAR", a[i], "at", i)
		dp[i] = 2*dp[i-1]
		
		if a[i] in last:
			if verbosity > 2: print("before at pos", last[a[i]], "({}-{})".format(dp[i], dp[last[a[i]]]))
			dp[i] -= dp[last[a[i]]]
		
		last[a[i]] = i - 1

		if verbosity > 2:
			print("dp:", dp[i])
			print("last:", last[a[i]])

	# substract the starting value from result
	result = dp[n-1] - dp[-1]
	
	# lastly, remove the oil well used in calculi before printing debug info
	del(dp[-1])

	# end result debug info
	if verbosity > 1:
		print("\n### RESULT ###")
		print("str:", a)
		print("len:", repr(n))
		print("distinct chars:", len(last))
		print("last:", repr(last))
		print("distinct:", repr(dp))
		print("result:", result)

	if verbosity == 1:
		print(result)

	return result

# a simple loop around tester()
# looks very understandable :D
def loop(verbosity=3):
	while True:
		t = input("> ")
		if t == "": break
		tester(t, verbosity)

# an advanced loop around tester()
def mass(n):
	q = {}
	for i in range(n):
		r = tester(bin(i)[2:])
		if r not in q:
			q[r] = []
		q[r].append(i)

	# clean them
	q = {i: clean(j) for i, j in q.items()}
	return q

# test cleansing func
def clean(a):
	# first: take just the shortest
	e = [bin(i)[2:] for i in a]
	r = len(min(e, key=len))
	a = [i for i in e if len(i) == r]

	# second: clear repetitive answers
	# thats some heavily modified for loop here
	i = 0
	while True:
		if len(a) <= i:
			break

		# pop reversed copies
		if a[i][::-1] != a[i] and a[i][::-1] in a:
			a.pop(i)
			continue
		i += 1

	return a

### TEST AREA ENDS ###

# lets module thihs
if __name__ == 'niam'[::-1].join(['_'*2]*2):
	print(main(int(input())))

# an empty line in end of script cuz why not?

Test 1

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: WRONG ANSWER

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: WRONG ANSWER

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: WRONG ANSWER

Test 11

Group: 2

Verdict: ACCEPTED

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED

Test 14

Group: 2

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 2

Verdict: ACCEPTED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 3

Verdict: ACCEPTED

Test 22

Group: 3

Verdict: ACCEPTED

Test 23

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 3

Verdict: ACCEPTED

Test 25

Group: 3

Verdict: ACCEPTED

Test 26

Group: 3

Verdict: ACCEPTED

Test 27

Group: 3

Verdict: ACCEPTED

Test 28

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 29

Group: 3

Verdict: ACCEPTED

Test 30

Group: 3

Verdict: ACCEPTED

Test 31

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 32

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 33

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 34

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 35

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 36

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 37

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 38

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 39

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 40

Group: 4

Verdict: TIME LIMIT EXCEEDED