Suppose you have an integer $v$. In one operation, you can:

either set $v = (v + 1) mod 32768$

or set $v = (2 \cdot v) mod 32768$.

You are given $n$ integers $a_1, a_2, \dots, a_n$. What is the minimum number of operations you need to make each $a_i$ equal to $0$?


-----Input-----

The first line contains the single integer $n$ ($1 \le n \le 32768$) — the number of integers.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i < 32768$).


-----Output-----

Print $n$ integers. The $i$-th integer should be equal to the minimum number of operations required to make $a_i$ equal to $0$.


-----Examples-----

Input
4
19 32764 10240 49
Output
14 4 4 15


-----Note-----

Let's consider each $a_i$:

$a_1 = 19$. You can, firstly, increase it by one to get $20$ and then multiply it by two $13$ times. You'll get $0$ in $1 + 13 = 14$ steps.

$a_2 = 32764$. You can increase it by one $4$ times: $32764 \rightarrow 32765 \rightarrow 32766 \rightarrow 32767 \rightarrow 0$.

$a_3 = 10240$. You can multiply it by two $4$ times: $10240 \rightarrow 20480 \rightarrow 8192 \rightarrow 16384 \rightarrow 0$.

$a_4 = 49$. You can multiply it by two $15$ times.

Source: codeforces | Difficulty: EASY
Tags: Bit manipulation

Graph algorithms

Graph traversal

Shortest paths

Complete search

Greedy algorithms

Dynamic programming


Solutions:
import sys

def solve():
	MOD = 32768
	dp = [None] * MOD
	dp[0] = 0
	q = [0]
	qi = 0
	while qi < len(q):
		x = q[qi]
		qi += 1
		tmp = [(x - 1) % MOD]
		if x % 2 == 0:
			tmp.append(x // 2)
			tmp.append(x // 2 + MOD // 2)
		for y in tmp:
			if dp[y] is None:
				dp[y] = dp[x] + 1
				q.append(y)
	inp = sys.stdin.readline
	n = int(inp())
	print(' '.join((str(dp[i]) for i in map(int, inp().split()))))

def main():
	solve()
main()


T = int(input())
outp = []
global md
md = 32768
global dct
dct = md * [-1]
dct[0] = 0

def maxdiv(i):
	p = 0
	while not i % 2 ** p:
		p += 1
	return p - 1

def val(i):
	if dct[i] >= 0:
		return dct[i]
	else:
		optA = 1 + val((i + 1) % md)
		optB = 15 - maxdiv(i)
		vl = min(optA, optB)
		dct[i] = vl
		return vl
for i in range(md - 1, 0, -1):
	_ = val(i)
A = [int(c) for c in input().split(' ')]
for n in A:
	outp.append(dct[n])
print(' '.join([str(c) for c in outp]))


N = 32768
dp = [0] * (N + 1)
st = [0] * (N + 1)
q = [N]
st[0] = 1
dp[0] = 0
st[q[0]] = 1
while q:
	uq = []
	for i in q:
		if not st[i - 1]:
			uq.append(i - 1)
			dp[i - 1] = dp[i] + 1
			st[i - 1] = 1
		if not i % 2:
			(a, b) = (i // 2, (i + 32768) // 2)
			if not st[a]:
				uq.append(a)
				dp[a] = dp[i] + 1
				st[a] = 1
			if not st[b]:
				uq.append(b)
				dp[b] = dp[i] + 1
				st[b] = 1
	q = uq
dp[N] = 1
n = int(input())
ll = list(map(int, input().split()))
for i in range(N + 1):
	if 16 == dp[i]:
		print(i)
for i in ll:
	print(dp[i], end=' ')


n = int(input())
a = map(int, input().split())
c = 32768
arr = [[] for i in range(c)]
for i in range(c):
	arr[(i + 1) % c].append(i)
	arr[2 * i % c].append(i)
dist = [-1] * c
active = [0]
counter = 0
while len(active) != 0:
	nextactive = []
	for at in active:
		if dist[at] == -1:
			dist[at] = counter
			for e in arr[at]:
				nextactive.append(e)
	active = nextactive.copy()
	counter += 1
for j in a:
	print(dist[j], end=' ')


lim = 32768
dp = [15] * lim
dp[0] = 0
for i in range(1, lim):
	b = bin(i)
	b = b[::-1]
	for j in range(len(b)):
		if b[j] == '1':
			dp[i] = 15 - j
			break
dp[-1] = 1
i = 32766
while i > 0:
	dp[i] = min(dp[i], dp[i + 1] + 1)
	i -= 1
n = int(input())
arr = list(map(int, input().split()))
for z in arr:
	print(dp[z], end=' ')
print()


def calc():
	to_do = [32768]
	res[32768] = 0
	res[0] = 0
	n = []
	full = dict()
	while to_do:
		old = to_do[0]
		n.clear()
		if old > 0:
			n.append(old - 1)
		if not old & 1 and old:
			n.append(old // 2)
			n.append((32768 + old) // 2)
		to_do.pop(0)
		tmp = res[old]
		for item in n:
			if res[item] == 'a':
				res[item] = res[old] + 1
				full[item] = res[old] + 1
				to_do.append(item)
				if item > 32767:
					item = item % 32768
					res[item] = res[old] + 1
					full[item] = res[old] + 1
					to_do.append(item)
n = int(input())
res = ['a'] * 32769
calc()
a = [int(x) for x in input().split()]
for i in a:
	print(res[i], end=' ')


import copy
import math

def xx(y):
	s = bin(y)
	an = 0
	for i in reversed(range(len(s))):
		if s[i] == '1':
			an = i
			break
	return len(s) - an
d = [100000000] * 32769
d[32768] = 0
d[0] = 0
for i in reversed(range(32768)):
	d[i] = min(d[i + 1] + 1, 16 - xx(i))
d[0] = 0
ka = int(input())
a = list(map(int, input().split()))
ans = []
for i in a:
	ans.append(d[i])
print(*ans)


from collections import *
ans = 32768
a = [-1 for i in range(ans + 8)]
l = [[] for i in range(ans + 8)]
s = deque([])
for i in range(ans):
	l[(i + 1) % ans].append(i)
	l[i * 2 % ans].append(i)
a[0] = 0
s.append(0)
while s:
	x = s.popleft()
	for temp in l[x]:
		if a[temp] == -1:
			a[temp] = a[x] + 1
			s.append(temp)
for _ in range(1):
	n = int(input())
	l = list(map(int, input().split()))
	for i in l:
		print(a[i], end=' ')


import collections
n = int(input())
a = list(map(int, input().strip().split()))
graph = collections.defaultdict(list)
MOD = 32768
for i in range(1, MOD):
	graph[(i + 1) % MOD].append(i)
	graph[(i << 1) % MOD].append(i)
que = collections.deque([0])
dist = [0] * MOD
while que:
	curNode = que.popleft()
	for nxtNode in graph[curNode]:
		if dist[nxtNode] == 0:
			que.append(nxtNode)
			dist[nxtNode] = dist[curNode] + 1
for i in range(n):
	print(dist[a[i]], end=' ')


def solvecff():
	n = int(input())
	lis = [int(i) for i in input().split()]
	from collections import defaultdict
	a = {i: -1 for i in range(32768)}
	mod = 32768
	l = [[i] for i in range(mod)]
	for i in range(mod):
		l[(i + 1) % mod].append(i)
		l[i * 2 % mod].append(i)
	a[0] = 0
	s = []
	s.append(0)
	while len(s) != 0:
		x = s[0]
		s.pop(0)
		for tmp in l[x]:
			if a[tmp] == -1:
				a[tmp] = a[x] + 1
				s.append(tmp)
	ans = []
	for i in lis:
		ans.append(str(a[i]))
	print(' '.join(ans))
solvecff()


seen = set()
cost = {}
m = 2 ** 15
queue = [(0, 0)]
while len(queue) > 0:
	(v, distance) = queue.pop(0)
	if v in seen:
		continue
	seen.add(v)
	cost[v] = distance
	if v % 2 == 0:
		queue.append(((v + m) // 2, distance + 1))
		queue.append((v // 2, distance + 1))
	queue.append(((v - 1) % m, distance + 1))
n = int(input())
a = map(int, input().split())
print(' '.join([str(cost[x]) for x in a]))


import functools
LIM = 32768

@functools.lru_cache(None)
def _solve_with_2(n):
	a = 0
	while n:
		n = n % LIM * 2 % LIM
		a += 1
	return a

@functools.lru_cache(None)
def solve(n):
	if n == 0:
		return 0
	return min(1 + solve((n + 1) % LIM), _solve_with_2(n))
n = int(input())
for i in range(LIM - 1, -1, -1):
	solve(i)
arr = list(map(int, input().split()))
print(' '.join(list(map(str, map(solve, arr)))))


import heapq

def solution(m):
	ans = {i: 20 for i in range(m)}
	ans[0] = 0
	visited = set()
	q = [(0, 0)]
	while q:
		(d, r) = heapq.heappop(q)
		if not r in visited:
			visited.add(r)
			ans[r] = d
		a = (r - 1) % m
		if not a in visited:
			heapq.heappush(q, (d + 1, a))
		if r % 2 == 0:
			(b, c) = (r // 2, (m + r) // 2)
			if not b in visited:
				heapq.heappush(q, (d + 1, b))
			if c != b and (not c in visited):
				heapq.heappush(q, (d + 1, c))
	return ans
n = int(input())
l = [int(k) for k in input().split(' ')]
distances = solution(32768)
d = [distances[k] for k in l]
ans = ''
for c in d:
	ans += ' '
	ans += str(c)
print(ans[1:])


import sys
input = lambda : sys.stdin.readline()[:-1]
ni = lambda : int(input())
na = lambda : list(map(int, input().split()))
yes = lambda : print('yes')
Yes = lambda : print('Yes')
YES = lambda : print('YES')
no = lambda : print('no')
No = lambda : print('No')
NO = lambda : print('NO')
n = ni()
m = 32768
dist = [float('inf') for i in range(m)]
dist[0] = 0
from collections import deque
dq = deque([0])
g = [[] for i in range(m)]
for i in range(m):
	g[(i + 1) % m].append(i)
	g[i * 2 % m].append(i)
while dq:
	e = dq.popleft()
	for f in g[e]:
		if dist[f] == float('inf'):
			dist[f] = dist[e] + 1
			dq.append(f)
a = na()
print(*[dist[a[i]] for i in range(n)])


import math

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	pre = [0 for i in range(32769)]
	for i in range(1, 32769):
		ans = 0
		n = i
		while n % 32768 != 0:
			ans += 1
			n = n * 2
		pre[i] = ans
	for i in range(2, 32769):
		x = 1
		j = i - 1
		while j >= 1 and pre[j] > pre[i] + x:
			pre[j] = pre[i] + x
			x += 1
			j -= 1
	ans = []
	for x in arr:
		ans.append(pre[x])
	print(*ans)
solve()


dp = [15] * 32768
for i in range(1, 32768):
	x = i
	n = 0
	while x > 0:
		n += 1
		x = x * 2 % 32768
	dp[i] = n
dp[0] = 0
dp[32767] = 1
i = 32766
while i > 0:
	dp[i] = min(dp[i], dp[i + 1] + 1)
	i -= 1
n = int(input())
arr = list(map(int, input().split()))
for z in arr:
	print(dp[z], end=' ')
print()


answers = [15] * 32768
for i in range(0, 32768):
	x = i
	n = 0
	while x > 0:
		n += 1
		x = x * 2 % 32768
	answers[i] = n
answers[32767] = 1
for i in reversed(range(1, 32767)):
	t = answers[i + 1] + 1
	if t < answers[i]:
		answers[i] = t
n = int(input())
a = list(map(int, input().split()))
for x in a:
	print(answers[x], end=' ')
print()


def fill(pow):
	d = [pow for _ in range(2 ** pow)]
	d[0] = 0
	for p in range(pow, 0, -1):
		for k in range(2 ** (pow - p)):
			d[k * 2 ** p] = min(d[k * 2 ** p], pow - p)
	return d
pow = 15
mod = 2 ** pow
d = fill(pow)
n = int(input())
a = [int(x) for x in input().split()]
ans = []
for i in range(n):
	opts = [d[(a[i] + j) % mod] + j for j in range(pow)]
	ans.append(min(opts))
print(*ans, sep=' ')


def get_two(num):
	n = num
	tws1 = 0
	while not n % 2 == 1:
		tws1 += 1
		n //= 2
	return tws1
input()
num = map(int, input().split())
num = list(num)

def get_min(n):
	if n == 0:
		return 0
	ans = 15
	for i in range(15):
		ans1 = i + 15 - get_two(n + i)
		if ans1 < ans:
			ans = ans1
	return ans
print(*[get_min(i) for i in num])


from queue import Queue
N = 32768
f = [0 if i == 0 else -1 for i in range(N)]
e = [[] for i in range(N)]
for i in range(N):
	e[(i + 1) % N].append(i)
	e[2 * i % N].append(i)
q = Queue()
q.put(0)
while q.qsize() != 0:
	u = q.get()
	for v in e[u]:
		if f[v] == -1:
			f[v] = f[u] + 1
			q.put(v)
input()
print(' '.join(map(lambda x: str(f[int(x)]), input().split())))


def count_two(element: int):
	count = 0
	while element % 2 == 0:
		count += 1
		element //= 2
		if count == 15:
			break
	return count

def calculate():
	op = []
	for i in range(N):
		minimum = float('inf')
		for j in range(15):
			if (arr[i] + j) % 2 == 0:
				a = count_two(arr[i] + j)
				ans = 15 - a
				ans += j
			else:
				ans = 15
			if ans < minimum:
				minimum = ans
		op.append(minimum)
	return op
N = int(input())
arr = list(map(int, input().split()))
print(' '.join(map(str, calculate())))


import sys, os.path
import math
if os.path.exists('Input.txt'):
	sys.stdin = open('Input.txt', 'r')
	sys.stdout = open('Output.txt', 'w')

def operation(a):
	if a == 0:
		return 0
	ans = float('inf')
	for i in range(15):
		(value, op) = (a + i, 0)
		while value % 2 == 0:
			value = value // 2
			op += 1
		ans = min(ans, 15 - op + i)
	return ans
n = int(input())
a = list(map(int, input().split()))
ans = [operation(i) for i in a]
print(*ans)


n = int(input())
l = [*map(int, input().split())]
step = 15
l1 = list((i for i in range(1, 16)))
A = lambda x: 2 ** x
l2 = list(map(A, l1))
for a in l:
	step_minus = 0
	for i in range(15):
		if a % l2[i] == 0:
			if step_minus < i + 1:
				step_minus = i + 1
		elif l2[i] - a % l2[i] < i + 1:
			if step_minus < i + 1 - (l2[i] - a % l2[i]):
				step_minus = i + 1 - (l2[i] - a % l2[i])
	print(step - step_minus, end=' ')


def CCircle(s1):
	for i in s1:
		if i == 0:
			print(0, end=' ')
			continue
		cnt = 15
		for addOneCnt in range(15):
			cur = i + addOneCnt
			pow_cnt = 0
			while cur % 2 == 0:
				cur = cur // 2
				pow_cnt += 1
			cnt = min(cnt, addOneCnt + (15 - pow_cnt))
		print(cnt, end=' ')
cases_cnt = int(input())
s1 = [int(x) for x in input().strip().split(' ')]
res = CCircle(s1)


n = int(input())
l = map(int, input().split())
ans = ''
for i in l:
	x = []
	for j in range(16):
		x.append(-i % 2 ** j + 15 - j)
	ans += str(min(x)) + ' '
print(ans)


from math import ceil, log
res = []
int(input())
l = list(map(int, input().split()))
c = 32768

def nexp(i, max):
	exp = ceil(log(i, 2))
	if 2 ** exp - i < 15 and 2 ** exp - i + 15 - exp < 15:
		return 2 ** exp - i + 15 - exp
	else:
		tmp = i
		steps = 0
		if i % 2 != 0:
			i += 1
			steps += 1
		while i % c != 0:
			if steps > max:
				return max + 1
			i *= 2
			steps += 1
		return steps

def minsteps(i):
	exp = ceil(log(i, 2))
	if i == 0:
		return 0
	else:
		steps = 15
		for j in range(15):
			tmp = j + i
			c = 0
			while tmp % 2 == 0:
				tmp /= 2
				c += 1
			steps = min(steps, j + 15 - c)
		return steps
s = ''
for i in l:
	if i == 0:
		s += '0 '
	else:
		steps = minsteps(i)
		s += str(steps) + ' '
print(s)


def solve(i, c):
	if i % 32768 == 0:
		return c
	while i:
		i = 2 * i % 32768
		c = c + 1
		if i == 0:
			break
	return c

def nextPowerOf2(n):
	n -= 1
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16
	n += 1
	return n
ans = [0 for i in range(32789)]
for i in range(1, 32789):
	ans[i] = solve(i, 0)
for _ in range(1):
	n = int(input())
	a = [int(i) for i in input().split()]
	A = []
	for i in a:
		np = nextPowerOf2(i)
		c = ans[i]
		for j in range(i + 1, i + 12):
			c = min(c, j - i + ans[j])
		c = min(c, np - i + ans[np])
		A.append(c)
	print(*A)


def ct(a):
	n = a
	ans = 0
	while n % 2 == 0 and n > 1:
		n //= 2
		ans += 1
	return ans
n = int(input())
l = list(map(int, input().split()))
ansl = list()
for i in range(n):
	step = 15
	if l[i] % 2 == 1:
		temp = l[i]
		pt = 1
		while pt <= 15:
			step = min(step, 15 - ct(l[i] + pt) + pt)
			pt += 2
	else:
		temp = l[i]
		pt = 0
		while pt < 15:
			step = min(step, 15 - ct(temp + pt) + pt)
			pt += 2
	ansl.append(min(step, (32768 - l[i]) % 32768))
print(*ansl)


def get_cnt(n):
	cnt = 0
	while n % 2 == 0:
		n //= 2
		cnt += 1
	return 15 - cnt

def solve():
	n = int(input())
	a = list(map(int, input().split(' ')))
	res = []
	for x in a:
		if x == 0:
			res.append(0)
			continue
		cnt = 15
		for j in range(16):
			cnt = min(cnt, get_cnt(x + j) + j)
		res.append(cnt)
	print(*res)
solve()


import random
t = int(input())
l = list(map(int, input().split()))
answers = []
for i in l:
	minmovement = None
	counter = 0
	if i == 0:
		answers.append('0')
		continue
	for j in range(i, i + 15):
		numof2inprimefactorisation = 0
		num = j
		c = 0
		while num % 2 == 0:
			num = num // 2
			c += 1
		if minmovement == None:
			minmovement = 15 - c + counter
		elif minmovement > 15 - c + counter:
			minmovement = 15 - c + counter
		counter += 1
	if i == 32768:
		minmovement = 1
	answers.append(str(minmovement))
print(' '.join(answers))


def check_2(num):
	res = 0
	while num > 0:
		if num % 2 == 0:
			num = num // 2
			res += 1
		else:
			break
	return res

def min_steps(num):
	if num == 0:
		return 0
	res = 15
	for i in range(15):
		cur = num + i
		res = min(res, i + 15 - check_2(cur))
	return res
n = int(input())
data = input().strip().split(' ')
data = [int(e) for e in data]
for e in data:
	print(min_steps(e), end=' ')


def berat(x):
	if x % 32768 == 0:
		return 15
	elif x % 16384 == 0:
		return 14
	elif x % 8192 == 0:
		return 13
	elif x % 4096 == 0:
		return 12
	elif x % 2048 == 0:
		return 11
	elif x % 1024 == 0:
		return 10
	elif x % 512 == 0:
		return 9
	elif x % 256 == 0:
		return 8
	elif x % 128 == 0:
		return 7
	elif x % 64 == 0:
		return 6
	elif x % 32 == 0:
		return 5
	elif x % 16 == 0:
		return 4
	elif x % 8 == 0:
		return 3
	elif x % 4 == 0:
		return 2
	elif x % 2 == 0:
		return 1
	else:
		return 0
n = int(input())
arr = list(map(int, input().split()))
dp = [0] * 32769
for i in range(1, 32769):
	dp[i] = berat(i)
for i in arr:
	min1 = 15
	if i == 0:
		print(0)
		continue
	for j in range(0, 15):
		if i + j > 32768:
			break
		temp = 15 - dp[i + j]
		min1 = min(min1, temp + j)
	print(min1, end=' ')


import collections
import math

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))
n = ii()
a = li()
ans = []
for i in a:
	if i == 0:
		ans.append(0)
		continue
	tmax = 0
	for j in range(16):
		t = 0
		s = i + j
		while s % 2 == 0:
			t += 1
			s //= 2
		if t > j:
			tmax = max(tmax, t - j)
	ans.append(15 - tmax)
print(*ans)


n = int(input())
ans = []
for value in map(int, input().split()):
	if value == 0:
		print(0)
		continue
	min_steps = float('inf')
	for x in range(1, 16):
		rem = value % (1 << x)
		min_steps = min(min_steps, ((1 << x) - rem if rem else 0) + (15 - x))
	print(min_steps, end=' ')


def main() -> None:
	MOD = 32768
	count = [-1] * MOD
	count[0] = 0
	for j in range(100):
		que = []
		for i in range(MOD):
			if count[i] != -1:
				continue
			if count[(i + 1) % MOD] != -1 or count[i * 2 % MOD] != -1:
				que.append(i)
		for i in que:
			count[i] = j + 1
	n = int(input())
	a = list(map(int, input().split()))
	res = [count[x] for x in a]
	print(*res)
main()


from collections import Counter, deque
import math
from random import randint
from bisect import bisect
import sys
import re
MOD = 32768
MAX = sys.maxsize
MIN = -sys.maxsize

class get:

	def int():
		return list(map(int, input().split()))

	def str():
		return input().split()

	def float():
		return list(map(float, input().split()))

	def map():
		return map(int, input().split())

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, sqrt(n)):
		if n % i == 0:
			return False
	return True

def find(n):
	ans = 16
	for i in range(17):
		x = n + i
		c = 0
		x %= MOD
		if x == 0:
			ans = min(ans, i)
			continue
		while x > 0 and x % 2 == 0:
			c += 1
			x = x // 2
		ans = min(i + 15 - c, ans)
	return ans

def solve():
	n = int(input())
	a = get.int()
	arr = []
	for item in a:
		arr.append(find(item))
	print(*arr)
solve()


n = int(input())
a = list(map(int, input().split()))
arr = []
for i in range(1, 32768 + 1):
	x = bin(i)
	x = x[2:]
	x = '00000000000000000000000000000' + x
	x = x[-16:]
	x = x[::-1]
	n2 = len(x)
	c1 = 0
	k = 0
	while k < n2:
		if x[k] == '0':
			c1 += 1
		else:
			break
		k += 1
	curans = 15 - c1
	arr.append(curans)
arr2 = []
for i in a:
	ans = 15
	for j in range(0, 16):
		if i + j > 32768:
			break
		tempans = arr[i + j - 1] + j
		ans = min(ans, tempans)
	arr2.append(ans)
print(*arr2)


def count_factor_2(n):
	count = 0
	while n > 0 and n % 2 == 0:
		count += 1
		n //= 2
	return count
tc = int(input())
for n in list(map(int, input().split())):
	if n == 0:
		print(0, end=' ')
		continue
	ans = 15
	for j in range(15):
		tn = n + j
		ans = min(ans, 15 - count_factor_2(tn) + j)
	print(ans, end=' ')


from base64 import b16decode
import sys, math

def f(n):
	if n == 0:
		return 0
	else:
		h = int(math.log(n, 2))
		if 2 ** h == n:
			return 15 - h
		else:
			x = 0
			b = 16
			y = 0
			for i in range(n, n + 15 + 1):
				y = i
				while y % 2 == 0:
					y = y // 2
					x = x + 1
				b = min(b, 15 - x + i - n)
				x = 0
			return b
input = sys.stdin.readline
m = int(input())
l = list(map(int, input().split()))
for i in range(m):
	print(f(l[i]), end=' ')
print()


def count(num):
	c = 0
	while num % 2 == 0:
		c += 1
		num = num // 2
	return c
n = int(input())
v = list(map(int, input().split()))
for i in v:
	if i == 0:
		print(0)
		continue
	ans = 15
	for j in range(16):
		ans = min(ans, 15 - count(i + j) + j)
	print(ans, end=' ')


n = input()
a = [int(i) for i in input().split()]
res = []
for k in a:
	possibilities = []
	for i in range(1, 16):
		puiss = 2 ** i
		rest = k % puiss
		possibilities += [(puiss - rest) * (rest != 0) + 15 - i]
	res += [min(possibilities)]
print(*res, sep=' ')


def pow_two(n):
	if n == 0:
		return 15
	p = 0
	while n % 2 == 0:
		n //= 2
		p += 1
	return p
n = int(input())
m = 32768
a = [int(s) for s in input().split()]
for i in range(n):
	maximum = 15
	j = 15
	while j > 0:
		step = 15 - j
		if 15 + step - pow_two(a[i] + step) < maximum:
			maximum = step + 15 - pow_two(a[i] + step)
		j -= 1
	print(maximum, end=' ')


import fileinput
import math

def find_two_representation(b):
	c = 1.0 * b
	twos = 0
	while c % 2 == 0:
		twos += 1
		c /= 2
	return (c, twos)

def minops(b):
	if b % 32768 == 0:
		return 0
	n = 15
	options = [b + i for i in range(0, n)]
	operations = [i for i in range(0, n)]
	for j in range(len(options)):
		(prefactor, num_twos) = find_two_representation(options[j])
		num_ops_left = n - num_twos
		operations[j] += num_ops_left
	return min(operations)

def getanswer(a):
	answer = [0] * len(a)
	for j in range(len(a)):
		answer[j] = minops(a[j])
	return answer

def solve():
	ins = []
	for line in fileinput.input():
		ins.append(line.strip('\n'))
	num_ints = ins[0]
	ints = [int(j) for j in ins[1].split(' ')]
	answer = getanswer(ints)
	out = ' '.join([str(j) for j in answer]) + ' '
	print(out)
solve()


from queue import Queue
from re import A
VAL = 32768
bfs_queue = Queue(0)
bfs_queue.put((VAL, 0))
dp = [-1] * (VAL + 5)
dp[0] = 0
while not bfs_queue.empty():
	val_top = bfs_queue.get()
	top = val_top[0]
	cnt = val_top[1]
	if dp[top] != -1:
		continue
	dp[top] = cnt
	bfs_queue.put(((top - 1) % VAL, cnt + 1))
	if top % 2 == 0:
		bfs_queue.put((top // 2, cnt + 1))
		bfs_queue.put(((top + VAL) // 2 % VAL, cnt + 1))
n = int(input())
a_list = list(map(int, input().split()))
result = [dp[a] for a in a_list]
print(*result, sep=' ')


import sys
input = sys.stdin.readline

def solve(n, arr):
	m = 2 ** 15
	ans = []
	hashmap = {}
	for i in range(n):
		val = float('inf')
		for j in range(arr[i], min(arr[i] + 15, m + 1)):
			if j in hashmap:
				cnt = hashmap[j]
				val = min(val, abs(j - arr[i]) + 15 - cnt)
				continue
			num = j
			cnt = 0
			for k in range(15, -1, -1):
				if num % 2 ** k == 0:
					cnt = k
					break
			hashmap[num] = cnt
			val = min(val, abs(j - arr[i]) + 15 - cnt)
		ans.append(val)
	print(*ans)
n = int(input())
arr = list(map(int, input().split()))
solve(n, arr)


def bc(n):
	x = 0
	if n == 0:
		return 0
	while n % 2 == 0:
		x += 1
		n = n // 2
	return 15 - x
n = int(input())
l = list(map(int, input().split()))
t = [float('inf') for _ in range(n)]
for i in range(n):
	for j in range(15):
		t[i] = min(t[i], j + bc(l[i] + j))
print(*t)


import math

def val(m):
	p = 0
	while m % 2 == 0:
		p += 1
		m //= 2
	return p
n = int(input())
l = list(map(int, input().split()))
for i in range(n):
	op = 15
	if l[i] == 0:
		op = 0
	else:
		for j in range(16):
			op = min(15 - val(l[i] + j) + j, op)
	print(op, end=' ')


import math
import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
l = [0] * 32769
for i in range(1, 32769):
	j = 0
	min1 = 0
	while j <= 15:
		s = i + j
		c = 0
		while s % 2 == 0:
			s = s // 2
			c += 1
		if c - j > min1:
			min1 = abs(c - j)
		j += 1
	l[i] = 15 - min1
n = inp()
a = li()
for i in a:
	prl(l[i])


n = int(input())
a = [int(x) for x in input().split()]
for x in a:
	t = 2
	ans = 15
	for i in range(15):
		p = x % t
		if p == 0:
			ans = min(ans, 14 - i)
		p = t - p
		ans = min(ans, p + 14 - i)
		t <<= 1
	print(ans, end=' ')


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	ans = []
	for i in range(n):
		if A[i] == 0:
			ans.append(0)
			continue
		moves = 15
		for add in range(16):
			num = A[i] + add
			for two_pow in range(16):
				if num % 2 == 1:
					moves = min(moves, 15 - two_pow + add)
					break
				num = num // 2
		ans.append(moves)
	print(*ans)
t = 1
while t != 0:
	solve()
	t -= 1


from math import log2
input()
for x in map(int, input().split()):
	ans = 15
	for i in range(15):
		a = 1
		n = x + i
		while n & 1 != 1 and a <= 15:
			a += 1
			n >>= 1
		ans = min(15 - a + i, ans)
	print(ans + 1, end=' ')


from sys import stdin, stdout

def to_bit(x):
	return bin(x)[2:]

def trailing_zeros(n):
	if n == 0:
		return 15
	s = str(to_bit(n))
	return len(s) - len(s.rstrip('0'))

def cal(x):
	return min((15 - trailing_zeros(x + i) + i for i in range(16)))

def solve():
	n = int(stdin.readline().strip())
	a = list(map(int, stdin.readline().strip().split()))
	a = [cal(x) for x in a]
	ans = ' '.join(map(str, a))
	print(ans)
solve()


n = int(input())
arr = list(map(int, input().split()))
lst = []
for i in arr:
	k = 16
	for j in range(16):
		n2 = 0
		m = i + j
		while m % 2 == 0 and n2 < 15:
			m = m // 2
			n2 += 1
		k = min(k, j + 15 - n2)
	lst.append(str(k))
print(' '.join(lst))


n = int(input())
arr = [int(x) for x in input().split()]
lis = [15 for i in range(32770)]
lis[0] = 0
for i in range(1, 32769):
	num = i
	m = 15
	for j in range(15):
		temp = num + j
		count = 0
		while temp % 2 == 0 and temp > 0:
			count += 1
			temp //= 2
		m = min(m, 15 - count + j)
	lis[num] = m
for item in arr:
	print(lis[item], end=' ')


import math
n = int(input())
x = list(map(int, input().split()))
for i in range(n):
	a = x[i]
	if a == 0:
		print(0, end=' ')
		continue
	if 32768 % a == 0:
		print(int(math.log(32768 // a, 2)), end=' ')
		continue
	m = 0
	for i in range(16):
		c = 0
		z = a + i
		while z % 2 == 0:
			z = z // 2
			c += 1
		m = max(c - i, m)
	print(min(15, 15 - m), end=' ')


def count_twos(num):
	c = 0
	while num > 0:
		if num % 2 == 0:
			num = num // 2
			c += 1
		else:
			break
	return c
n = int(input())
anslist = ''
list1 = [int(num) for num in input().split()]
for i in range(0, len(list1)):
	num1 = list1[i]
	if num1 == 32768:
		anslist += str(1) + ' '
	elif num1 == 0:
		anslist += str(0) + ' '
	else:
		two_list = [count_twos(num1)]
		for i in range(1, 16):
			temp = num1 + i
			two_list.append(count_twos(temp))
		moves_list = []
		for i in range(0, 16):
			moves = i + (15 - two_list[i])
			moves_list.append(moves)
		anslist += str(min(moves_list)) + ' '
print(anslist.strip())


lst = []
for i in range(16):
	lst.append(pow(2, i))
n = int(input())
a = list(map(int, input().split()))
for i in a:
	if i == 0:
		print(0, end=' ')
		continue
	x = 0
	for j in range(15):
		if lst[j] > i:
			x = j
	ans1 = 15
	for k in range(1, j + 2):
		if i % lst[k] == 0:
			ans = 15 - k
		else:
			ans = (i // lst[k] + 1) * lst[k] - i + 15 - k
		ans1 = min(ans1, ans)
	print(ans1, end=' ')


n = int(input())
arr = input().split(' ')
for i in range(n):
	temp1 = int(arr[i])
	if temp1 == 0:
		print(0, end=' ')
	else:
		ans = 16
		for j in range(16):
			temp2 = temp1 + j
			cnt = 0
			while temp2 % 2 == 0:
				cnt += 1
				temp2 = temp2 // 2
			res = j + 15 - cnt
			ans = min(ans, res)
		print(ans, end=' ')
print()


import math
n = int(input())
arr = list(map(int, input().split()))
ans = []

def twos(x):
	count = 0
	for i in range(15):
		if x // 2 == x / 2:
			x = x // 2
			count += 1
		else:
			return count
	return count
for x in arr:
	arr = []
	for i in range(15):
		arr.append(twos(x + i) - i)
	ans.append(15 - max(arr))
print(*ans)


import math

def f2(x):
	pow2 = x & ~(x - 1)
	return int(math.log(pow2, 2))
n = int(input())
l = list(map(int, input().split()))
for i in l:
	if i == 0:
		print(0, end=' ')
	else:
		nf2 = f2(i)
		minn = 15 - nf2
		if minn <= 0:
			print(0, end=' ')
		else:
			for j in range(1, minn + 1):
				if 15 + j - f2(i + j) < minn:
					minn = j + 15 - f2(i + j)
			print(minn, end=' ')


n = int(input())
a = list(map(int, input().split()))
for x in a:
	temp1 = x
	if x == 0:
		print(0)
		continue
	arr = [0] * 16
	i = 0
	while x:
		arr[i] = x % 2
		x = x // 2
		i += 1
	ans = min(15, 32768 - temp1)
	p = 1
	temp = 1
	t = -1
	for i in range(16):
		if arr[i] == 1:
			if t == -1:
				t = i
			p = 1
		else:
			ans = min(ans, temp + 15 - i)
			temp += 2 ** i
	ans = min(ans, 15 - t)
	print(ans, end=' ')


import math
n = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(n):
	ans1 = 15
	for j in range(0, 16):
		x = math.gcd(32768, a[i] + j)
		y = math.log(x, 2)
		ans1 = min(ans1, j + (15 - y))
	ans.append(int(ans1))
print(*ans)


import sys
a = int(input())
b = [int(i) for i in input().split()]
mod = 32768
out = []
for i in range(a):
	mi = 999999
	if b[i] % mod == 0:
		out.append(0)
		continue
	for j in range(0, 16):
		tpow = 0
		m = b[i] + j
		while m % 2 == 0:
			tpow += 1
			m //= 2
		mi = min(mi, j + 15 - tpow)
	out.append(mi)
for i in out:
	print(i, end=' ')
print()


import math
n = int(input())
l = list(map(int, input().split()))
for i in l:
	if i != 0:
		ans = 15
	else:
		print(0, end=' ')
		continue
	for j in range(0, 16):
		op1 = j
		op2 = 15
		if (i + j) % 2 == 0:
			count = 0
			x = i + j
			while x != 0 and x % 2 == 0:
				x = x // 2
				count += 1
			op2 = op2 - count
		ans = min(ans, op1 + op2)
	print(ans, end=' ')


from math import inf
n = int(input())
a = [int(x) for x in input().split()]

def greatestbinfactor(x):
	s = 0
	m = x
	while 1:
		(m, mod) = divmod(m, 2)
		if mod:
			break
		s += 1
	return s

def ispower2(x):
	q = x
	while q > 1:
		(q, mod) = divmod(q, 2)
		if mod:
			return False
	return True
for x in a:
	if x == 0:
		print(0, end=' ')
	else:
		res = 15
		for i in range(res):
			k = x + i
			gbf = greatestbinfactor(k)
			mx = -1
			if gbf > mx:
				mx = gbf
			res = min(res, 15 - gbf + i)
		print(res, end=' ')
print()


n = int(input())
nums = input().split(' ')
MOD = 32768
for i in nums:
	k = int(i)
	if k == 0:
		print('0', end=' ')
		continue
	K = k
	ans = 15
	for j in range(1, 16):
		k = K + j
		cnt = 0
		while k % 2 == 0 and k != 0:
			cnt += 1
			k = int(k / 2)
		ans = min(ans, 15 + j - cnt)
	if K % 2 == 0:
		k = K
		cnt = 0
		while k % 2 == 0 and k != 0:
			cnt += 1
			k = int(k / 2)
		ans = min(ans, 15 - cnt)
	print(ans, end=' ')
print()


n = int(input())
a = [int(x) for x in input().split()]
for i in a:
	if i == 0:
		print(0, end=' ')
	else:
		ans = 32769
		for j in range(16):
			x = i + j
			cnt = 0
			while x % 2 == 0:
				cnt += 1
				x = x // 2
			calc = j + 15 - cnt
			ans = min(ans, calc)
		print(ans, end=' ')
print()


dp = [32769] * 32768
dp[0] = 0
for cycle in range(20):
	for x in reversed(range(32768)):
		dp[x] = min(dp[x], min(dp[(x + 1) % 32768], dp[2 * x % 32768]) + 1)
n = int(input())
a = [int(x) for x in input().split()]
b = [str(dp[x]) for x in a]
print(' '.join(b))


l = int(input())
a = list(map(int, input().split()))
mod = 32768
for n in a:
	I = n
	ans = 15
	cnt = 0
	for i in range(15):
		temp = str(bin(I))[::-1]
		ans = min(ans, 15 - temp.find('1') + cnt)
		cnt += 1
		I += 1
	if n == 0:
		ans = 0
	print(ans, end=' ')