You are given an integer $n$. In $1$ move, you can do one of the following actions:

erase any digit of the number (it's acceptable that the number before the operation has exactly one digit and after the operation, it is "empty");

add one digit to the right.

The actions may be performed in any order any number of times.

Note that if, after deleting some digit from a number, it will contain leading zeroes, they will not be deleted. E.g. if you delete from the number $301$ the digit $3$, the result is the number $01$ (not $1$).

You need to perform the minimum number of actions to make the number any power of $2$ (i.e. there's an integer $k$ ($k \ge 0$) such that the resulting number is equal to $2^k$). The resulting number must not have leading zeroes.

E.g. consider $n=1052$. The answer is equal to $2$. First, let's add to the right one digit $4$ (the result will be $10524$). Then let's erase the digit $5$, so the result will be $1024$ which is a power of $2$.

E.g. consider $n=8888$. The answer is equal to $3$. Let's erase any of the digits $8$ three times. The result will be $8$ which is a power of $2$.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

Each test case consists of one line containing one integer $n$ ($1 \le n \le 10^9$).


-----Output-----

For each test case, output in a separate line one integer $m$ — the minimum number of moves to transform the number into any power of $2$.


-----Examples-----

Input
12
1052
8888
6
75
128
1
301
12048
1504
6656
1000000000
687194767
Output
2
3
1
3
0
0
2
1
3
4
9
2


-----Note-----

The answer for the first test case was considered above.

The answer for the second test case was considered above.

In the third test case, it's enough to add to the right the digit $4$ — the number $6$ will turn into $64$.

In the fourth test case, let's add to the right the digit $8$ and then erase $7$ and $5$ — the taken number will turn into $8$.

The numbers of the fifth and the sixth test cases are already powers of two so there's no need to make any move.

In the seventh test case, you can delete first of all the digit $3$ (the result is $01$) and then the digit $0$ (the result is $1$).

Source: codeforces | Difficulty: EASY
Tags: String algorithms

Mathematics

Greedy algorithms


Solutions:
def chk(a, b):
	i = 0
	j = 0
	cmn = 0
	for i in a:
		if i == b[j]:
			cmn += 1
			j += 1
			if j >= len(b):
				break
	return len(a) + len(b) - 2 * cmn
i = 1
lst = []
while i <= 1e+19:
	lst.append(str(i))
	i *= 2
for _ in range(int(input())):
	s = input()
	ans = 1e+19
	for i in lst:
		ans = min(ans, chk(s, i))
	print(ans)


import sys
from sys import stdin, stdout
from math import ceil, floor, sqrt, log, log2, log10
from collections import Counter
int_max = float('inf')
int_min = -float('inf')
ANS = []
input = stdin.readline

def solve():
	pass

def lcs(X, Y):
	n = len(X)
	m = len(Y)
	maxx = int_min
	for t in range(1):
		it = t
		total = 0
		for j in range(n):
			if it < m and X[j] == Y[it]:
				it += 1
				total += 1
		maxx = max(maxx, total)
	return maxx
t = int(input())
for i in range(t):
	n = int(input())
	s = str(n)
	minn = int_max
	for i in range(100):
		t = str(2 ** i)
		l = lcs(s, t)
		minn = min(minn, len(s) - l + len(t) - l)
	print(minn)
print('\n'.join(ANS))


import math, sys
for _ in range(int(input())):
	n = input()
	ans = 10 ** 10
	for i in range(64):
		a = 2 ** i
		s = str(a)
		j = 0
		c = 0
		for i in n:
			if i == s[j]:
				c += 1
				j += 1
			if len(s) == j:
				break
		ans = min(ans, len(n) - c + len(s) - c)
	print(ans)


def solve(n):
	min_number_change = 1 + len(n) - 2 * longest_subseq_of_m_in_n('1', n)
	length = 0
	k = 0
	while length < 2 * len(n) + 1:
		candidate = str(2 ** k)
		length = len(candidate)
		k += 1
		if len(candidate) + len(n) - 2 * longest_subseq_of_m_in_n(candidate, n) < min_number_change:
			min_number_change = len(candidate) + len(n) - 2 * longest_subseq_of_m_in_n(candidate, n)
	return min_number_change

def longest_subseq_of_m_in_n(m, n):
	position = -1
	embedded_letters = 0
	for letter in m:
		nextpos = n[position + 1:].find(letter)
		if nextpos > -1:
			position += nextpos + 1
			embedded_letters += 1
		else:
			return embedded_letters
	return embedded_letters
t = int(input())
mylist = []
for i in range(t):
	mylist.append(str(input()))
for n in mylist:
	print(solve(n))


NUM_POWERS = 100
Powers = []

def FindN(x, p):
	ps = Powers[p]
	psl = len(ps)
	xs = str(x)
	xsl = len(xs)
	xn = ''
	xnl = 0
	pi = 0
	xi = 0
	n = 0
	while xi < xsl and pi < psl:
		if xs[xi] == ps[pi]:
			xn = xn + xs[xi]
			xnl += 1
			xi += 1
			pi += 1
		else:
			xi += 1
			n += 1
	if xi == xsl and pi == psl:
		n += psl - xnl
	elif pi == psl:
		n += xsl - xi
	else:
		n += psl - xnl
	return n
p = 1
for i in range(0, NUM_POWERS):
	Powers.append(str(p))
	p *= 2
num_trials = int(input())
for i in range(0, num_trials):
	x = int(input())
	min_n = 100000000
	for j in range(0, NUM_POWERS):
		n = FindN(x, j)
		if n < min_n:
			min_n = n
	print(min_n)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	p = str(n)
	t = len(p)
	ans = t + 1
	for i in range(64):
		s = str(pow(2, i))
		m = len(s)
		j = 0
		c = 0
		for k in p:
			if j < m and k == s[j]:
				j += 1
				c += 1
		ans = min(ans, t - c + m - c)
	print(ans)


import sys
from os import path

def getInput():
	return sys.stdin.readline().strip()

def getInt():
	return int(getInput())

def getInts():
	return map(int, getInput().split())

def getArray():
	return list(getInts())
if path.exists('Input.txt'):
	sys.stdin = open('Input.txt', 'r')
	sys.stdout = open('Output.txt', 'w')
sys.setrecursionlimit(10 ** 5)
(MOD, MOD2, INF) = (10 ** 9 + 7, 998244353, 10 ** 18)
tc = 1
tc = getInt()
powers = [str(1 << i) for i in range(62)]
for _ in range(tc):
	string = getInput()
	lens = len(string)
	ans = 27
	for power in powers:
		news = ''
		s = p = 0
		while s < len(string) and p < len(power):
			if string[s] == power[p]:
				news += power[p]
				p += 1
			s += 1
		dels = max(0, len(string) - len(news))
		adds = max(0, len(power) - len(news))
		ops = dels + adds
		if ops < ans:
			ans = ops
	print(ans)


import math
import sys
input = sys.stdin.readline
k = math.log(10 ** 18, 2)
for _ in range(int(input())):
	n = int(input())
	mins = []
	for i in range(int(k), -1, -1):
		a = str(2 ** i)
		idx = 0
		res = 0
		for x in str(n):
			if x == a[idx]:
				idx += 1
				res += 1
			if idx == len(a):
				break
		mins.append(len(str(n)) - res + len(a) - idx)
	mins.append(len(str(n)) + 1)
	print(min(mins))


p = {}
i = 1
while i <= 10 ** 18:
	p[str(i)] = True
	i *= 2

def f(a, b):
	i = 0
	j = 0
	k = 0
	while i < len(b) and j < len(a):
		while j < len(a) and a[j] != b[i]:
			j += 1
		if i < len(b) and j < len(a) and (a[j] == b[i]):
			k += 1
		i += 1
		j += 1
	return len(a) + len(b) - 2 * k
for _ in range(int(input())):
	n = input()
	if p.get(n) != None:
		print(0)
		continue
	a = 10 ** 10
	for i in p:
		a = min(a, f(n, i))
		if a == 1:
			break
	print(a)


a = int(input())
for i in range(a):
	b = input()
	z = 1
	obs = 1000000000
	for j in range(60):
		x = str(z)
		k = 0
		for m in range(len(b)):
			if b[m] == x[k]:
				k += 1
			if k == len(x):
				break
		obs = min(obs, len(b) - k + len(x) - k)
		z *= 2
	print(obs)


import sys
input = sys.stdin.readline
t = int(input())
p2 = []
k = 1
while k < 10 ** 18:
	p2.append(k)
	k *= 2
for _ in range(t):
	n = int(input())
	sn = str(n)
	min_cnt = 10 ** 9
	for x in p2:
		xx = str(x)
		j = 0
		cnt_del = 0
		cnt_add = 0
		for i in range(len(xx)):
			if j >= len(sn):
				cnt_add += len(xx) - i
				break
			if xx[i] == sn[j]:
				j += 1
			else:
				while j < len(sn) and xx[i] != sn[j]:
					j += 1
					cnt_del += 1
				if j < len(sn):
					j += 1
				else:
					cnt_add += len(xx) - i
					break
		if len(sn) > len(xx):
			cnt_add += len(sn) - j
		cnt = cnt_del + cnt_add
		min_cnt = min(min_cnt, cnt)
	print(min_cnt)


l = []
x = 1
while x < 1e+18:
	l.append(str(x))
	x *= 2
t = int(input())
for _ in range(t):
	n = input()
	dis = 100
	for i in range(len(l)):
		ans = 0
		aux = 0
		j = 0
		while j < len(n):
			if aux >= len(l[i]):
				break
			if l[i][aux] == n[j]:
				aux += 1
			else:
				ans += 1
			j += 1
		if aux >= len(l[i]):
			ans += len(n) - j + 1
		else:
			ans += len(l[i]) - aux + 1
		dis = min(dis, ans)
	print(dis - 1)


t = int(input())
l = [str(2 ** i) for i in range(60)]

def lcs(a, b):
	n = 0
	for i in a:
		try:
			if i == b[n]:
				n += 1
		except:
			return n
	return n
for aslkjdklasj in range(t):
	tmp = input()
	flag = 0
	ans = 999999
	for i in l:
		ans = min(ans, len(i) + len(tmp) - 2 * lcs(tmp, i))
	print(min(len(tmp) + 1, ans))


import sys
from math import factorial, gcd
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest, nsmallest
from itertools import groupby
from copy import deepcopy
MOD = 10 ** 9 + 7
INF = float('inf')
rl = lambda : list(map(int, sys.stdin.readline().split()))
rs = lambda : sys.stdin.readline().strip()
power2 = [1]
i = 1
for _ in range(60):
	power2.append(power2[-1] << 1)

def countDiff(num, two):
	(num, two) = (str(num), str(two))
	i = 0
	diff = 0
	for j in range(len(num)):
		if two[i] == num[j]:
			i += 1
		else:
			diff += 1
		if i == len(two):
			diff += len(num) - j - 1
			break
	diff += len(two) - i
	return diff
for _ in range(int(input())):
	n = int(input())
	print(min([countDiff(n, x) for x in power2]))


import sys
input = sys.stdin.readline

def main():
	S = input().strip()
	ans = 10 ** 10
	n = len(S)
	for T in lst:
		p = 0
		for s in S:
			if s == T[p]:
				p += 1
		ans = min(ans, n + len(T) - 1 - 2 * p)
	print(ans)
lst = []
x = 1
while x <= 10 ** 20:
	lst.append(str(x) + '=')
	x *= 2
for _ in range(int(input())):
	main()


bi = [str(2 ** i) for i in range(55)]

def solve(a, b):
	l = len(a)
	l2 = len(b)
	if l > 2 * l:
		return l + 1
	j = 0
	for el in a:
		if el == b[j]:
			j += 1
		if j == l2:
			break
	return min(l + 1, l - 2 * j + l2)
for _ in range(int(input())):
	a = input()
	print(min([solve(a, x) for x in bi]))


(a, x) = ([], 1)
while x < 10 ** 18:
	a.append(str(x))
	x <<= 1

def solve(n):
	sol = len(n) + 1
	for x in a:
		i = 0
		for c in n:
			if i < len(x) and x[i] == c:
				i += 1
		erase = len(n) - i
		add = len(x) - i
		sol = min(sol, erase + add)
	return sol
t = int(input())
for _ in range(t):
	n = int(input())
	print(solve(str(n)))


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def main():
	p2 = [str(2 ** i) for i in range(68)]
	t = int(input())
	for _ in range(t):
		n = input()
		sol = float('inf')
		for i in p2:
			idx = 0
			for j in n:
				if j == i[idx]:
					idx += 1
				if idx == len(i):
					break
			sol = min(sol, len(n) - idx + (len(i) - idx))
		print(sol)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math
from collections import *
from functools import lru_cache
inf = float('inf')
p2 = []
i = 1
while i <= 10 ** 18:
	p2.append(str(i))
	i *= 2

@lru_cache(None)
def solve(n, s):
	nx = sx = 0
	nt = 0
	while nx < len(n) and sx < len(s):
		if n[nx] == s[sx]:
			nx += 1
			sx += 1
		else:
			nx += 1
			nt += 1
	return nt + len(s) - sx + len(n) - nx
for _ in range(int(input())):
	n = input()
	print(min((solve(n, x) for x in p2)))


r = [str(2 ** x) for x in range(55)]

def min_dif(str1, str2):
	c1 = 0
	c2 = 0
	for i in range(len(str1)):
		if str1[i] == str2[c2]:
			c1 += 1
			c2 += 1
			if c2 == len(str2):
				break
	return len(str1) - c1 + len(str2) - c1
for _ in range(int(input())):
	n = str(input())
	print(min([min_dif(n, i) for i in r]))


a = [str(2 ** i) for i in range(64)]

def min_dif(n, ri):
	c = 0
	it = 0
	for i in n:
		if i == ri[it]:
			it += 1
			c += 1
			if it == len(ri):
				break
	return len(n) - c + len(ri) - c
for _ in range(int(input())):
	n = str(input())
	print(min([min_dif(n, i) for i in a]))


tw = 1
l = []
lnll = 0
while tw < 10 ** 17:
	tmp = tw
	l1 = []
	while tmp > 0:
		l1.insert(0, tmp % 10)
		tmp = tmp // 10
	l.append(l1)
	tw = 2 * tw
	lnll += 1
lnl = []
for a in l:
	lnl.append(len(a))
t = int(input())
for _ in range(t):
	n = int(input())
	l1 = []
	ln1 = 0
	while n > 0:
		l1.insert(0, n % 10)
		n = n // 10
		ln1 += 1
	digit = [[], [], [], [], [], [], [], [], [], []]
	idx = [0] * lnll
	for i in range(lnll):
		digit[l[i][idx[i]]].append(i)
	for d in l1:
		tmp = digit[d]
		digit[d] = []
		for j in tmp:
			idx[j] += 1
			if idx[j] < lnl[j]:
				digit[l[j][idx[j]]].append(j)
	M = 100
	for i in range(lnll):
		M = min(M, lnl[i] + ln1 - 2 * idx[i])
	print(M)


def check(s, po):
	l1 = list(str(s))
	l2 = list(str(po))
	i = 0
	j = 0
	d = 0
	while i < len(l1) and j < len(l2):
		if l1[i] == l2[j]:
			j = j + 1
		i = i + 1
	d = d + len(l1) - j
	d = d + len(l2) - j
	return d

def solve():
	s = int(input())
	ans = 1000000000
	for i in p:
		ans = min(ans, check(s, i))
	print(ans)
p = []
for i in range(64):
	p.append(2 ** i)
for testis in range(int(input())):
	solve()


t = int(input())
eta = [str(2 ** z) for z in range(65)]
for i in range(t):
	n = input()
	z = len(n)
	mn = 100
	for j in eta:
		res = 0
		c = list(n[::-1])
		v = list(j)
		y = 0
		for k in v:
			while c and k != c[-1]:
				c.pop()
			if not c:
				break
			else:
				c.pop()
				y += 1
		res = len(j) - y + len(n) - y
		mn = min(mn, res)
	print(mn)


from sys import stdin, stdout

def getSteps(num, twos):
	steps = 0
	i = 0
	for digit in num:
		if digit == twos[i]:
			i += 1
		if i == len(twos):
			break
	return len(num) + len(twos) - 2 * i
twosarr = ['576460752303423488', '288230376151711744', '144115188075855872', '72057594037927936', '36028797018963968', '18014398509481984', '9007199254740992', '4503599627370496', '2251799813685248', '1125899906842624', '562949953421312', '281474976710656', '140737488355328', '70368744177664', '35184372088832', '17592186044416', '8796093022208', '4398046511104', '2199023255552', '1099511627776', '549755813888', '274877906944', '137438953472', '68719476736', '34359738368', '17179869184', '8589934592', '4294967296', '2147483648', '1073741824', '536870912', '268435456', '134217728', '67108864', '33554432', '16777216', '8388608', '4194304', '2097152', '1048576', '524288', '262144', '131072', '65536', '32768', '16384', '8192', '4096', '2048', '1024', '512', '256', '128', '64', '32', '16', '8', '4', '2', '1']
for _ in range(int(stdin.readline())):
	n = stdin.readline().strip()
	stdout.write(str(min((getSteps(n, twos) for twos in twosarr))) + '\n')


def match(S, T):
	j = 0
	for i in S:
		if j == len(T):
			return len(S) + len(T) - 2 * j
		if i == T[j]:
			j += 1
	return len(S) + len(T) - 2 * j
T = int(input())
for _ in range(T):
	N = input()
	m = 1000000000.0
	for i in range(65):
		o = match(N, str(2 ** i))
		m = min(m, o)
	print(m)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import bisect as bs
p = ['1']
i = 1
while i <= 10 ** 18:
	i *= 2
	p.append(str(i))
for i in range(int(input())):
	n = int(input())
	s = str(n)

	def cnt(x, y):
		i = 0
		j = 0
		n = len(x)
		m = len(y)
		while i < n and j < m:
			if x[i] == y[j]:
				i += 1
				j += 1
			else:
				j += 1
		return n - i + m - i
	ans = 10 ** 5
	x = 0
	for i in p:
		if cnt(i, s) < ans:
			ans = cnt(i, s)
			x = i
	print(ans)


a = []
i = 1

def similarity(xt):
	x = []
	while xt != 0:
		x.append(xt % 10)
		xt = xt // 10
	x.reverse()
	res = -1
	for tw in a:
		ix = 0
		simil = 0
		for (elx, el) in enumerate(tw):
			incl = False
			while ix < len(x):
				if x[ix] == el:
					simil += 1
					incl = True
				ix += 1
				if incl:
					break
			if not incl or elx == len(tw) - 1 or ix == len(x):
				newRes = len(tw) + len(x) - 2 * simil
				if res == -1 or newRes < res:
					res = newRes
	return res
while i < 10 ** 18 + 1:
	t = []
	ti = i
	while ti != 0:
		t.append(ti % 10)
		ti = ti // 10
	t.reverse()
	a.append(t)
	i = i * 2
n = int(input())
lst = []
for i in range(0, n):
	ele = int(input())
	print(similarity(ele))


from sys import stdin, stdout

class SOLVE:

	def solve(self):
		try:
			f = open('input.txt')
			R = f.readline
		except:
			R = stdin.readline
		W = stdout.write
		twos = []
		for k in range(64):
			twos.append(str(2 ** k))
		ans = []
		for _ in range(int(R())):
			n = R()[:-1]
			mn = 99999999999
			for two in twos:
				i = j = 0
				leni = len(n)
				lenj = len(two)
				cnt = leni + lenj
				while i < leni and j < lenj:
					if n[i] == two[j]:
						cnt -= 2
						j += 1
					i += 1
				mn = min(mn, cnt)
			ans.append(str(mn))
		W('\n'.join(ans))
		return 0

def main():
	s = SOLVE()
	s.solve()
main()


import sys
input = sys.stdin.readline
l = ['1' for _ in range(68)]
for i in range(1, 68):
	l[i] = str(int(l[i - 1]) * 2)

def comparestr(s, idx):
	i = 0
	j = 0
	same = 0
	if s == l[idx]:
		return 0
	for i in range(len(s)):
		if j >= len(l[idx]):
			break
		if s[i] == l[idx][j]:
			same += 1
			j += 1
			continue
	d = len(s) - same
	ins = len(l[idx]) - same
	return d + ins
for _ in range(int(input())):
	inp = input()
	ans = 100000000
	for i in range(67):
		temp = comparestr(inp, i)
		ans = min(ans, temp)
	print(ans - 1)


l = []
for i in range(70):
	l.append(str(2 ** i))
for _ in range(int(input())):
	x = input()
	ans = 11
	for i in range(70):
		y = l[i]
		jj = 0
		k = 0
		for j in range(len(x)):
			if k >= len(y):
				break
			if y[k] == x[j]:
				jj += 1
				k += 1
		ans = min(ans, len(x) + len(y) - 2 * jj)
	print(ans)


import atexit, io, sys, math, heapq

def get_int():
	return int(sys.stdin.readline().strip())

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

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

def get_string():
	return sys.stdin.readline().strip()

def write_int(a):
	sys.stdout.write(str(a) + '\n')

def write_str(a):
	sys.stdout.write(a + '\n')

def write_list(arr):
	sys.stdout.write(' '.join(map(str, arr)) + '\n')

def swap(arr, a, b):
	arr[a] ^= arr[b]
	arr[b] ^= arr[a]
	arr[a] ^= arr[b]

def int_len(a):
	return math.floor(math.log(a, 10)) + 1

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def Sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	res = []
	for i in range(2, len(prime)):
		if prime[i]:
			res.append(i)
	return res

def binarySearch(arr, l, r, x):
	if r >= l:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			return binarySearch(arr, l, mid - 1, x)
		else:
			return binarySearch(arr, mid + 1, r, x)
	else:
		return -1

def search(arr, x):
	return binarySearch(arr, 0, len(arr) - 1, x)

def toString(A):
	return ''.join(A)

def arrSum(Arr):
	Sum = 0
	for i in range(len(Arr)):
		Sum += Arr[i]
	return Sum

def compare(_from, _to):
	steps = 0
	i = 0
	j = 0
	while i < len(_from) and j < len(_to):
		if _from[i] != _to[j]:
			steps += 1
		else:
			i += 1
		j += 1
	return steps + len(_to) + len(_from) - i - j
arr = [0] * 65
j = 0
while j < 65:
	arr[j] = 2 ** j
	j += 1
p = int(input())
while p > 0:
	N = input()
	min = 99999999
	for i in range(len(arr)):
		res = compare(str(arr[i]), N)
		if res < min:
			min = res
	print(min)
	p -= 1


import sys
tokens = ''.join(sys.stdin.readlines()).split()[::-1]

def next():
	return tokens.pop()

def nextInt():
	return int(next())

def nextFloat():
	return float(next())

def getIntArray(n):
	return [nextInt() for _ in range(n)]

def getFloatArray(n):
	return [nextFloat() for _ in range(n)]

def getStringArray(n):
	return [next() for _ in range(n)]
flush = sys.stdout.flush
testcase = True

def solve(testcase=1):
	pass

	def calculate(s, t):
		d = p = 0
		for c in s:
			if p < len(t) and t[p] == c:
				p += 1
			else:
				d += 1
		return d + len(t) - p
	N = next()
	ans = 999999999999999999999999999999999999999999999999999999999999999999999999999999999
	for i in range(70):
		ans = min(ans, calculate(N, str(1 << i)))
	print(ans)
if testcase is None:
	while tokens:
		solve()
else:
	testcaseCount = nextInt() if testcase else 1
	for tc in range(testcaseCount):
		solve(tc + 1)
	assert not tokens


pat = []
for i in range(60):
	pat.append(1 << i)
T = int(input())

def solve(x, y):
	(x, y) = (str(x), str(y))
	(ans, i) = (0, 0)
	for c in y:
		while i < len(x) and x[i] != c:
			i += 1
		if i < len(x):
			ans += 1
			i += 1
		else:
			break
	return len(x) + len(y) - 2 * ans
for t in range(T):
	n = int(input())
	ans = min((solve(n, k) for k in pat))
	print(ans)


powers = [1 << k for k in range(60)]

def make_equal(n, p):
	n = str(n)
	p = str(p)
	cost = 0
	n = list(n)
	p = list(p)
	for j in range(len(p)):
		if j < len(n) and n[j] == p[j]:
			continue
		if j >= len(n):
			n.append(p[j])
			cost += 1
		else:
			while j < len(n) and n[j] != p[j]:
				n.pop(j)
				cost += 1
			if j >= len(n):
				n.append(p[j])
				cost += 1
	while n != p:
		n.pop()
		cost += 1
	return cost
for _ in range(int(input())):
	n = int(input())
	ans = float('inf')
	for p in powers:
		ans = min(ans, make_equal(n, p))
	print(ans)


arr = [1]
for i in range(100):
	arr.append(arr[-1] * 2)
for i in range(len(arr)):
	arr[i] = str(arr[i])

def lcs(s, t):
	n = len(s)
	m = len(t)
	c = 0
	ind = 0
	for i in range(n):
		if ind < m and s[i] == t[ind]:
			ind += 1
			c += 1
	return c
for _ in range(int(input())):
	n = int(input())
	s = str(n)
	k = len(s)
	ans = 10 ** 10
	for i in arr:
		m = len(i)
		c = lcs(s, i)
		ans = min(ans, k - c + m - c)
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = input()
	len_ = len(n)
	i = 1
	a = []
	while i <= 2 ** 100:
		a.append(str(i))
		i = i * 2
	ans = 100
	for i in range(len(a)):
		count = 0
		k = 0
		l = 0
		while l < len(n) and k < len(a[i]):
			if n[l] == a[i][k]:
				count = count + 1
				k = k + 1
			l = l + 1
		ans = min(ans, len_ + len(a[i]) - 2 * count)
	print(ans)


def solve(p, q):
	i = 0
	z = 0
	for x in p:
		if q[i] == x:
			z += 1
			i += 1
			if i == len(q):
				break
	z = z * 2
	return len(p) + len(q) - z
for _ in range(int(input())):
	k = input()
	m = 30
	j = 0
	while 2 ** j <= 2 ** 60:
		q = str(2 ** j)
		z = solve(k, q)
		m = min(m, z)
		j += 1
	print(m)


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
import math as mt
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)
mod = int(1000000000.0) + 7

def power(k, n):
	if n == 0:
		return 1
	if n % 2:
		return power(k, n - 1) * k % mod
	t = power(k, n // 2)
	return t * t % mod

def totalPrimeFactors(n):
	count = 0
	if n % 2 == 0:
		count += 1
		while n % 2 == 0:
			n //= 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			count += 1
			while n % i == 0:
				n //= i
		i += 2
	if n > 2:
		count += 1
	return count

def main():
	for _ in range(int(input())):
		n = int(input())
		ans = float('inf')
		s = str(n)
		for k in range(64):
			f = str(1 << k)
			i = 0
			j = 0
			while i < len(f) and j < len(s):
				if f[i] == s[j]:
					i += 1
				j += 1
			ans = min(ans, len(f) - i + len(s) - i)
		print(ans)
	return
main()


t = int(input())
power2 = [str(2 ** i) for i in range(68)]
while t:
	n = input()
	mxres = 9999999
	for num in power2:
		i = 0
		j = 0
		while i < len(n) and j < len(num):
			if n[i] == num[j]:
				j += 1
			i += 1
		tmp = len(n) - j + len(num) - j
		if tmp < mxres:
			mxres = tmp
	print(mxres)
	t -= 1


l = [1]
for i in range(1, 70):
	l.append(l[i - 1] * 2)
for i in range(int(input())):
	n = list(input())
	mx = 1000
	for i in l:
		i = str(i)
		f = j = k = h = 0
		while j < len(i) and k < len(n):
			if i[j] == n[k]:
				h += 1
			else:
				j -= 1
				f += 1
			k += 1
			j += 1
		if len(i) < len(n):
			f += len(n) - k
		mx = min(mx, f + (len(i) - h))
	print(mx)


import sys
input = lambda : sys.stdin.readline().strip()
powers = ['1']
while int(powers[-1]) < 10 ** 18:
	powers.append(str(int(powers[-1]) * 2))

def lcs(a, b):
	i = 0
	j = 0
	while i < len(a) and j < len(b):
		if a[i] == b[j]:
			i += 1
			j += 1
		else:
			i += 1
	return j
t = int(input())
while t:
	t -= 1
	n = input()
	ans = len(n) + 1
	for i in powers:
		no_rem = lcs(n, i)
		rem = len(n) - no_rem
		ans = min(ans, rem + len(i) - no_rem)
	print(ans)


ali = 0
from collections import defaultdict, Counter, deque
ali = 0
ali = 0
ali = 0
from math import sqrt, log10, log, floor, factorial
ali = 0
ali = 0
ali = 0
from bisect import bisect_left, bisect_right
ali = 0
ali = 0
ali = 0
from itertools import permutations, combinations
ali = 0
ali = 0
ali = 0
import sys, io, os
ali = 0
ali = 0
ali = 0
input = sys.stdin.readline
ali = 0
ali = 0
ali = 0
ali = 0
ali = 0
ali = 0
ali = 0
inf = float('inf')
ali = 0
ali = 0
ali = 0
mod = 10 ** 9 + 7
ali = 0
ali = 0

def yn(a):
	print('YES' if a else 'NO')
	ali = 0
ali = 0
ali = 0
ceil = lambda a, b: (a + b - 1) // b
ali = 0
ali = 0

def diff(a, b):
	ali = 0
	iter1 = 0
	ali = 0
	ali = 0
	ali = 0
	iter2 = 0
	ali = 0
	ali = 0
	ali = 0
	ans = 0
	ali = 0
	ali = 0
	while iter1 < len(a) and iter2 < len(b):
		ali = 0
		if a[iter1] == b[iter2]:
			ali = 0
			iter1 += 1
			ali = 0
			ali = 0
			ali = 0
			iter2 += 1
			ali = 0
			ali = 0
		else:
			ali = 0
			ans += 1
			ali = 0
			ali = 0
			ali = 0
			iter1 += 1
			ali = 0
			ali = 0
	while iter2 < len(b):
		ali = 0
		iter2 += 1
		ali = 0
		ali = 0
		ali = 0
		ans += 1
		ali = 0
		ali = 0
	while iter1 < len(a):
		ali = 0
		iter1 += 1
		ali = 0
		ali = 0
		ali = 0
		ans += 1
		ali = 0
		ali = 0
	ali = 0
	ali = 0
	ali = 0
	return ans
	ali = 0
	ali = 0
ali = 0
l = [str(2 ** i) for i in range(70)]
ali = 0
ali = 0
ali = 0
t = int(input())
ali = 0
ali = 0
for i in range(t):
	ali = 0
	n = input().strip()
	ali = 0
	ali = 0
	ali = 0
	mina = inf
	ali = 0
	ali = 0
	for i in l:
		ali = 0
		theta = diff(n, i)
		ali = 0
		ali = 0
		ali = 0
		if mina > theta:
			ali = 0
			mina = theta
			ali = 0
			ali = 0
	ali = 0
	print(mina)
	ali = 0
	ali = 0


r = [str(2 ** i) for i in range(60)]

def f(x, s):
	c = 0
	index = 0
	for i in x:
		if i == s[index]:
			index += 1
			c += 1
			if index == len(s):
				break
	return len(x) + len(s) - 2 * c
t = int(input())
for _ in range(t):
	n = str(input())
	ans = 100
	for i in r:
		ans = min(ans, f(n, i))
	print(ans)


import sys
input = sys.stdin.readline
s = [str(2 ** i) for i in range(62)]
t = int(input())
for _ in range(t):
	n = input().split()[0]
	min_changes = len(n) + 1
	for num in s:
		ind = 0
		keep = 0
		for s1 in num:
			if s1 not in n[ind:]:
				break
			s1_ind = n[ind:].index(s1) + ind + 1
			ind = s1_ind
			keep += 1
		change = len(n) - keep + len(num) - keep
		min_changes = min(min_changes, change)
	print(min_changes)


from collections import Counter, deque, defaultdict
from heapq import *
import math

def inp():
	return int(input())

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

def arrInput():
	return list(map(int, input().split()))
memo = []

def pre():
	global memo
	for i in range(70):
		memo.append(str(1 << i))

def findOper(n, m):
	(i, j) = (0, 0)
	(nlen, mlen) = (len(n), len(m))
	remove = 0
	while i < nlen and j < mlen:
		if n[i] == m[j]:
			i += 1
			j += 1
		else:
			j += 1
			remove += 1
	remove += mlen - j
	add = nlen - i
	return add + remove

def task():
	global memo
	n = input()
	nlen = len(n)
	minOper = math.inf
	for i in range(len(memo)):
		minOper = min(minOper, findOper(memo[i], n))
	print(min(minOper, nlen + 1))
pre()
for _ in range(inp()):
	task()


def min_diff(n, i):
	x = 0
	y = 0
	for j in n:
		if j == i[y]:
			y += 1
			x += 1
			if y == len(i):
				break
	return len(n) - x + len(i) - x
powers2 = [str(2 ** i) for i in range(60)]
for _ in range(int(input())):
	n = str(input())
	ans = 100
	for i in powers2:
		ans = min(ans, min_diff(n, i))
	print(ans)


def pref(a, b):
	i = 0
	j = 0
	while i < len(a) and j < len(b):
		if a[i] == b[j]:
			i += 1
			j += 1
		else:
			i += 1
	return j

def main():
	t = int(input())
	for tc in range(t):
		n = int(input())
		cur = 1
		res = len(str(n)) + 1
		for i in range(62):
			match = pref(str(n), str(cur))
			cost = len(str(cur)) - match + len(str(n)) - match
			if cost < res:
				res = cost
			cur = cur * 2
		print(res)
main()


def solve(num):
	n = len(num)
	result = float('inf')
	for k in range(60):
		temp = str(2 ** k)
		n_t = len(temp)
		cur = 0
		pnt = 0
		for x in num:
			if pnt < n_t and x != temp[pnt]:
				cur += 1
			elif pnt >= n_t:
				cur += 1
			else:
				pnt += 1
		result = min(result, cur + (n_t - pnt))
	print(result)
for _ in range(int(input())):
	solve(input())


import math
import heapq
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
H = 1000000000 + 7

def lcs(s1, s2):
	n = len(s1)
	m = len(s2)
	j = 0
	for i in range(n):
		if j < m and s1[i] == s2[j]:
			j += 1
	return m - j + (n - j)
p = 1
l = []
e = pow(10, 18)
while p <= e:
	l.append(p)
	p *= 2
for _ in range(I()):
	n = I()
	ln = len(str(n))
	m = math.inf
	for i in range(len(l)):
		p = len(str(l[i]))
		temp = lcs(str(n), str(l[i]))
		m = min(temp, m)
	print(m)


MAX = 987654321
t = int(input())
for _ in range(t):
	number = input()
	answer = MAX
	for two in range(60):
		two = str(2 ** two)
		(idx, cost) = (0, 0)
		for t in two:
			while idx < len(number) and number[idx] != t:
				idx += 1
			if idx < len(number) and number[idx] == t:
				cost += 1
				idx += 1
		answer = min(answer, len(number) + len(two) - cost * 2)
	print(answer)


p_2 = [str(2 ** k) for k in range(62)]

def cost(e, n):
	cst = 0
	cur = 0
	for (idx, c) in enumerate(n):
		if cur < len(e) and c == e[cur]:
			cur += 1
		else:
			cst += 1
	cst += len(e) - cur
	return cst
t = int(input())
for _ in range(t):
	n = input()
	n = str(n)
	ans = 20
	for e in p_2:
		ans = min(ans, cost(e, n))
	print(ans)


import sys
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
input = sys.stdin.readline

def minDistance(n, subword):
	j = 0
	operations = 0
	for i in range(len(n)):
		if j < len(subword) and n[i] == subword[j]:
			j += 1
		else:
			operations += 1
	operations += len(subword) - j
	return operations
T = int(input())
while T:
	T -= 1
	n = str(int(input().strip()))
	powers_of_two = [str(2 ** i) for i in range(64)]
	ans = float('inf')
	for word in powers_of_two:
		ans = min(ans, minDistance(n, word))
	print(ans)


import sys
from collections import defaultdict
input = sys.stdin.readline

def ri():
	return [int(i) for i in input().split()]

def rs():
	return input().split()[0]

def how_many(a, tgt):
	(i, j) = (0, 0)
	matched = 0
	while i < len(a) and j < len(tgt):
		if a[i] == tgt[j]:
			matched += 1
			j += 1
		i += 1
	return matched

def main():
	t = ri()[0]
	for _ in range(t):
		n = rs()
		mi = len(n) + 1
		p = 1
		while p < 2 ** 61:
			s = str(p)
			matched = how_many(n, s)
			deleted = len(n) - matched
			mi = min(mi, deleted + len(s) - matched)
			p *= 2
		print(mi)
main()


r = [str(2 ** i) for i in range(60)]

def min_dif(x, s):
	c = 0
	it = 0
	for i in x:
		if i == s[it]:
			it += 1
			c += 1
			if it == len(s):
				break
	return len(x) - c + len(s) - c
for _ in range(int(input())):
	n = str(input())
	print(min([min_dif(n, i) for i in r]))


from sys import stdin, stdout
ip = lambda : stdin.readline().rstrip('\r\n')
ips = lambda : ip().split()
out = lambda x, end='\n': stdout.write(str(x) + end)
a = ['1']
x = 1
for i in range(64):
	x *= 2
	a.append(str(x))
for _ in range(int(input())):
	n = input()
	count = []
	for x in a:
		i = j = c = 0
		while i < len(n) and j < len(x):
			if n[i] == x[j]:
				j += 1
			else:
				c += 1
			i += 1
		c += len(x) - j + len(n) - i
		count.append(c)
	print(min(count))


def ras(a, b):
	ans = 0
	i = 0
	while i < len(b) and ans < len(a):
		if a[ans] == b[i]:
			ans += 1
		i += 1
	return len(a) + len(b) - ans * 2
a = [1, 2]
while a[-1] < 10 ** 19:
	a.append(a[-1] * 2)
for _ in range(int(input())):
	ans = 11
	n = input()
	for i in range(len(a)):
		ans = min(ans, ras(str(a[i]), n))
	print(ans)


a = [str(2 ** i) for i in range(0, 100)]
for _ in range(int(input())):
	s = input()
	ans = 1000000000.0
	for number in a:
		(k1, k2) = (0, 0)
		d = 0
		while k1 < len(number) and k2 < len(s):
			if number[k1] != s[k2]:
				k2 += 1
				d += 1
			else:
				k1 += 1
				k2 += 1
		ans = min(ans, d + len(number) - k1 + len(s) - k2)
	print(ans)


def minEdit(string1: str, string2: str):
	j = 0
	answer = 0
	for (i, c) in enumerate(string1):
		if c != string2[j]:
			answer += 1
		else:
			j += 1
			if j == len(string2):
				break
	return answer + len(string2) - j + len(string1) - i - 1
powerOf2 = [str(2 ** i) for i in range(55)]
for _ in range(int(input())):
	string1 = input()
	print(min([minEdit(string1, string2) for string2 in powerOf2]))


import sys
arr = []

def arr_of_pow_2():
	arr[:] = [str(1 << i) for i in range(60)]

def make_a_power_of_two(x):
	is_x_pow_of_2 = x != 0 and x & x - 1 == 0
	if is_x_pow_of_2:
		sys.stdout.write(f'0\n')
		return
	x = str(x)
	(ans, x_size) = (sys.maxsize, len(x))
	for n in arr:
		y = str(n)
		y_size = len(str(n))
		(i, j, t) = (0, 0, 0)
		while i < x_size and j < y_size:
			if x[i] == y[j]:
				i += 1
				j += 1
			else:
				t += 1
				i += 1
		if i is x_size and j is not y_size:
			t += y_size - j
		elif i is not x_size and j is y_size:
			t += x_size - i
		ans = min(ans, t)
	sys.stdout.write(f'{ans}\n')
qt = int(sys.stdin.readline())
arr_of_pow_2()
for k in range(qt):
	qi = int(sys.stdin.readline())
	make_a_power_of_two(qi)


from collections import Counter
from functools import reduce
from math import acos, ceil, cos, floor, pi, sin, sqrt, log10
from random import random
from string import ascii_lowercase, ascii_uppercase, digits
from sys import exit, setrecursionlimit, stdin
dX = [-1, 1, 0, 0, -1, 1, -1, 1]
dY = [0, 0, -1, 1, 1, -1, -1, 1]
mod = int(1000000000.0 + 7)
eps = 1e-06
MAX = 3 * 10 ** 5 + 10
t = int(input())
twos = []
i = 1
while i < 10 ** 20:
	twos.append(str(i))
	i *= 2
for _ in range(t):
	n = input()
	minSteps = MAX
	for two in twos:
		(i, j) = (0, 0)
		while i < len(n) and j < len(two):
			if n[i] == two[j]:
				j += 1
			i += 1
		steps = len(n) + len(two) - 2 * j
		minSteps = min(minSteps, steps)
	print(minSteps)


ans = [1]
while ans[-1] <= pow(10, 19):
	ans.append(ans[-1] * 2)
import math
a = int(input())

def check(val, s):
	q = str(s)
	s = str(val)
	j = 0
	i = 0
	req = 0
	cnt = 0
	while j < len(q):
		if q[j] == s[i]:
			i += 1
			cnt += 1
		if i == len(s):
			break
		j += 1
	return len(q) - cnt + len(s) - cnt
for i in range(a):
	s = int(input())
	mini = math.inf
	for i in range(len(ans)):
		mini = min(check(ans[i], s), mini)
	print(mini)


t = int(input())
pows = []
for i in range(63):
	pows.append(str(2 ** i))
answer = []
for _ in range(t):
	n = input()
	ans = 10 ** 18
	for num in pows:
		ncopy = n
		count = 0
		for c in num:
			if c in ncopy:
				ind = ncopy.find(c)
				count += ind
				ncopy = ncopy[ind + 1:]
			else:
				ind = len(ncopy)
				count += ind + 1
				ncopy = ''
		count += len(ncopy)
		ans = min(ans, count)
	print(ans)


import math as _math
import sys as _sys

def _main():
	[tests_n] = _read_ints()
	for i_test in range(tests_n):
		[n] = _read_ints()
		result = how_many_moves_need_to_transform_to_the_power_of_two(n)
		print(result)

def how_many_moves_need_to_transform_to_the_power_of_two(x: int):
	assert x >= 1
	x_str = str(x)
	max_digits_n_allowed = len(x_str) * 2 + 1
	max_pattern_allowed = 10 ** max_digits_n_allowed - 1
	min_steps_n = _math.inf
	power_of_two = 1
	while power_of_two <= max_pattern_allowed:
		curr_steps_n = _find_distance(x_str, target=str(power_of_two))
		if curr_steps_n < min_steps_n:
			min_steps_n = curr_steps_n
		power_of_two *= 2
	return min_steps_n

def _find_distance(s, target):
	n_fit = 0
	moves_done = 0
	for ch in s:
		if n_fit < len(target) and ch == target[n_fit]:
			n_fit += 1
		else:
			moves_done += 1
	moves_done += len(target) - n_fit
	return moves_done

def _read_ints():
	return map(int, _read_string().split())

def _read_string():
	result = _sys.stdin.readline()
	assert result and result[-1] == '\n'
	return result[:-1]
_main()


def lcs(s1, p):
	j = 0
	matches = 0
	for c in p:
		j = s1.find(c, j) + 1
		if j == 0:
			break
		matches += 1
	return matches

def str_diff(s1, s2):
	intersection = lcs(s1, s2)
	return len(s1) + len(s2) - 2 * intersection
powers = [str(2 ** i) for i in range(54)]
n = int(input())
for _ in range(n):
	x = input()
	print(min((str_diff(x, s) for s in powers)))


import math
import copy
from decimal import *

def check(str, str1):
	i = 0
	j = 0
	ans = 0
	while i < len(str) and j < len(str1):
		if str[i] == str1[j]:
			i += 1
			j += 1
		else:
			i += 1
			ans += 1
	return ans + len(str) - i + len(str1) - j

def solve():
	t = 1
	t = int(input())
	for _ in range(t):
		a = []
		a.append(1)
		ans = 1
		for i in range(1, 60):
			ans *= 2
			a.append(ans)
		n = int(input())
		for i in range(0, 60):
			ans = min(ans, check(str(n), str(a[i])))
		print(ans)
solve()


def com(x, y):
	(lx, ly) = (len(x), len(y))
	now = 0
	for xx in x:
		if xx == y[now]:
			now += 1
		if now == ly:
			break
	return lx - now + ly - now
import sys
input = sys.stdin.readline
power = []
for i in range(60):
	power.append(str(2 ** i))
t = int(input())
for _ in range(t):
	n = input().rstrip('\n')
	ans = 20
	for i in power:
		ans = min(ans, com(n, i))
	print(ans)


from sys import stdin, stdout, maxsize
from math import sqrt, log, factorial as ft, gcd, ceil, floor
from collections import defaultdict
ii = lambda : int(input())
di = lambda : defaultdict(lambda : 0)
dl = lambda : defaultdict(lambda : list())
li = lambda : list(map(int, stdin.readline().strip().split()))
mi = lambda : map(int, stdin.readline().strip().split())
si = lambda : stdin.readline().strip()
for _ in range(ii()):
	n = ii()
	ans = -1
	f = 1
	s2 = str(n)
	l2 = len(s2)
	for i in range(60):
		s1 = str(f)
		l1 = len(s1)
		(i1, i2) = (0, 0)
		c = 0
		while i1 < l1 and i2 < l2:
			if s1[i1] == s2[i2]:
				c += 1
				i1 += 1
			i2 += 1
		temp = l2 - c + l1 - c
		if ans == -1:
			ans = temp
		else:
			ans = min(ans, temp)
		f *= 2
	print(ans)


t = int(input())

def common_sequence(a, powerOfTwo):
	a = str(a)
	powerOfTwo = str(powerOfTwo)
	potL = len(powerOfTwo)
	numSimilar = 0
	for i in a:
		if i == powerOfTwo[numSimilar]:
			numSimilar += 1
		if numSimilar == potL:
			break
	numToAdd = potL - numSimilar
	numToRemove = len(str(a)) - numSimilar
	return numToRemove + numToAdd
for i in range(t):
	n = int(input())
	powerOfTwo = 1
	ans = float('inf')
	for j in range(100):
		ans = min(common_sequence(n, powerOfTwo), ans)
		powerOfTwo *= 2
	ans = min(ans, len(str(n)) + 1)
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
l = [1]
c = 2
while c <= 10 ** 18:
	l.append(c)
	c *= 2
for _ in range(int(input())):
	s = str(input())
	ans = 40
	for i in range(len(l)):
		c = 0
		k = str(l[i])
		for j in range(len(s)):
			if k[c] == s[j]:
				c += 1
			if c == len(k):
				break
		ans = min(ans, len(s) - c + len(k) - c)
	print(ans)


import sys

def input():
	return sys.stdin.readline().rstrip('\r\n')

def maps():
	return [int(i) for i in input().split()]

def calc(s1, s2):
	word1 = str(s1)
	word2 = str(s2)
	if word1 == word2:
		return 0
	(n1, n2) = (len(word1), len(word2))
	i = 0
	dele = 0
	common = 0
	j = 0
	while j < n1 and i < n2:
		if word2[i] == word1[j]:
			j += 1
			common += 1
			i += 1
		else:
			j += 1
	add = n1 - common
	dele = dele + (n2 - i)
	return add + dele
arr = []
for i in range(60):
	arr.append(1 << i)
ok = False
for _ in range(*maps()):
	(n,) = maps()
	ans = n + 1
	ans2 = 1 << 60
	for i in range(60):
		ans = min(ans, calc(n, arr[i]))
	print(ans)


import sys

def digs(n):
	ans = []
	while n > 0:
		ans.append(n % 10)
		n //= 10
	return list(reversed(ans))
power2s = []
for k in range(71):
	power2s.append(digs(2 ** k))
nums = (int(tok) for tok in sys.stdin.read().split())
T = next(nums)
for i in range(T):
	n = next(nums)
	n_digs = digs(n)
	real_ans = 100
	for p2_digs in power2s:
		ans = 0
		for d in n_digs:
			if ans < len(p2_digs) and d == p2_digs[ans]:
				ans += 1
		real_ans = min(real_ans, len(n_digs) + len(p2_digs) - 2 * ans)
	print(real_ans)


import sys
input = sys.stdin.readline
P = [str(2 ** i) for i in range(100)]
t = int(input())
for tests in range(t):
	n = input().strip()
	ANS = 1 << 30
	for p in P:
		ind = 0
		for k in n:
			if ind < len(p) and k == p[ind]:
				ind += 1
		ANS = min(ANS, len(n) - ind + len(p) - ind)
	print(ANS)


import math
from collections import Counter
from functools import lru_cache
t = int(input())
for _ in range(t):
	arr = input()
	powers = [1]
	start = 1
	for i in range(1, 60):
		start *= 2
		powers.append(start)
	ans = len(arr) + 1
	for i in powers:
		s = str(i)
		common = 0
		for j in range(len(arr)):
			count = 0
			k = 0
			ind = 0
			while j + k < len(arr) and ind < len(s):
				if arr[j + k] == s[ind]:
					ind += 1
					count += 1
				k += 1
			common = max(common, count)
		temp = len(arr) - common
		temp += len(s) - common
		ans = min(ans, temp)
	print(ans)


import sys
INF = float('inf')
MOD = 10 ** 9 + 7
MOD2 = 998244353

def main():

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

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

	def LC():
		return list(input())

	def IC():
		return [int(c) for c in input()]

	def MI():
		return map(int, sys.stdin.readline().split())
	T = II()
	Two = [0] * 100
	for k in range(100):
		Two[k - 1] = list(str(2 ** k))
	for _ in range(T):
		N = LC()
		Ans = INF
		for k in range(100):
			two = Two[k]
			t = 0
			i = 0
			Ope = 0
			while i < len(N) and t < len(two):
				if N[i] == two[t]:
					i += 1
					t += 1
				else:
					i += 1
					Ope += 1
			if t < len(two):
				Ope += len(two) - t
			if i < len(N):
				Ope += len(N) - i
			Ans = min(Ans, Ope)
		print(Ans)
main()


import math
nums = list((str(math.floor(math.pow(2, k))) for k in range(60)))

def lcs(x, y):
	i = 0
	j = 0
	n = len(x)
	m = len(y)
	count = 0
	while i < n and j < m:
		if x[i] == y[j]:
			count += 1
			i += 1
			j += 1
		else:
			i += 1
	return n - count + max(m - count, 0)
for q_ in range(int(input())):
	n = input()
	res = 100
	for x in nums:
		match = lcs(n, x)
		if res > match:
			res = match
	print(res)


for _ in range(int(input())):
	num = str(input())
	power = 0
	len_of_num = len(num)
	ans = len_of_num + 1
	while True:
		power_of_2 = str(2 ** power)
		len_of_2 = len(power_of_2)
		if len_of_2 > 2 * len_of_num + 1:
			break
		good_nums = 0
		for char in num:
			if good_nums < len_of_2:
				if char == power_of_2[good_nums]:
					good_nums += 1
			else:
				break
		pos_ans = len_of_num - good_nums + len_of_2 - good_nums
		if pos_ans < ans:
			ans = pos_ans
		if ans == 0:
			break
		power += 1
	print(ans)


cmp = []
p = 1
while len(cmp) <= 64:
	cmp.append(str(p))
	p = p << 1
cmp.append(str(p))

def mss(x, y, n, m):
	ct = 0
	(i, j) = (0, 0)
	res = ''
	while i < n and j < m:
		if x[i] == y[j]:
			res += x[i]
			ct += 1
			i += 1
			j += 1
		else:
			i += 1
	return (ct, res)
T = int(input())
for t in range(T):
	n = input()
	cost = 20
	for i in range(len(cmp)):
		(lc, res) = mss(n, cmp[i], len(n), len(cmp[i]))
		if res and res[0] == '0':
			continue
		tcost = len(n) - lc + (len(cmp[i]) - lc)
		if tcost < cost:
			cost = tcost
			target = cmp[i]
	print(cost)


def count_ops(n, two_power):
	current = 0
	operations = 0
	for i in range(len(n)):
		if n[i] == two_power[current]:
			current += 1
		else:
			operations += 1
		if current >= len(two_power):
			return len(n) - current
	operations += len(two_power) - current
	return operations
num_requests = int(input())
a = 1
arr = [1]
while a < 10 ** 18 + 1:
	a *= 2
	arr.append(a)
for _ in range(num_requests):
	n = input()
	min_ops = 20
	for two_power in arr:
		min_ops = min(min_ops, count_ops(n, str(two_power)))
	print(min_ops)


(num, arr) = (1, [])
while len(str(num)) < 20:
	arr.append(str(num) + '#')
	num = num << 1
t = int(input())
for tc in range(t):
	n = str(input())
	res = 1 << 30
	for num in arr:
		(i, j, r) = (0, 0, 0)
		while i < len(n) and j < len(num):
			if n[i] == num[j]:
				j += 1
			else:
				r += 1
			i += 1
		res = min(res, 2 * r + len(num) - len(n) - 1)
	print(res)


def mutual(s1, s2):
	index = 0
	count = 0
	for i in s1:
		if len(s2) == index:
			return len(s1) - count + len(s2) - count
		if i == s2[index]:
			index += 1
			count += 1
	return len(s1) - count + len(s2) - count
pows = [1]
while pows[-1] < 1e+100:
	pows.append(pows[-1] * 2)
pows = [str(i) for i in pows]
for i in range(int(input())):
	k = input()
	m = float('inf')
	move = None
	for i in pows:
		count = mutual(k, i)
		if m > count:
			move = i
			m = count
	print(m)


def prefixMatch(s, p):
	i = 0
	for c in s:
		if i == len(p):
			break
		if c == p[i]:
			i += 1
	return i
twos = [1]
while twos[-1] * 2 <= 10 ** 20:
	twos.append(twos[-1] * 2)
twos = list(map(str, twos))
for _ in range(int(input())):
	n = input()
	print(min((len(x) + len(n) - 2 * prefixMatch(n, x) for x in twos)))


def closestpoweroftwo(lis1, n):
	lenn = len(n)
	list1 = []
	for i in lis1[:8 * lenn]:
		i = str(i)
		leni = len(i)
		k = 0
		count = 0
		x = 0
		for j in range(lenn):
			if k < leni:
				if n[j] == i[k]:
					k += 1
					x += 1
				else:
					x += 1
					count += 1
			else:
				break
		if k < leni:
			count += leni - k
		if x < lenn:
			count += lenn - x
		list1.append(count)
	return min(list1)
t = int(input())
ptwo = 1
lis1 = [1]
for i in range(80):
	ptwo = 2 * ptwo
	lis1.append(ptwo)
for i in range(t):
	n = input()
	ans = closestpoweroftwo(lis1, n)
	print(ans)


from sys import stdin, stdout, setrecursionlimit
from bisect import bisect_left, bisect_right
from math import ceil, floor, log, gcd
from collections import Counter, deque
from heapq import heappush, heappop, heapify
from operator import mul
from functools import reduce

def re():
	return stdin.readline().rstrip()

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

def test(cases):
	for _ in range(cases):
		solve()
mod = 1000000007

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(mul, range(n, n - r, -1), 1)
	denom = reduce(mul, range(1, r + 1), 1)
	return numer // denom

class Dsu:

	def __init__(self, n):
		self.parent = list(range(n))
		self.rank = [1] * n

	def find(self, x):
		while x != self.parent[x]:
			self.parent[x] = self.parent[self.parent[x]]
			x = self.parent[x]
		return x

	def union(self, x, y):
		(px, py) = (self.find(x), self.find(y))
		if px == py:
			return 0
		if self.rank[py] > self.rank[px]:
			(px, py) = (py, px)
		self.parent[py] = px
		self.rank[px] += self.rank[py]
		return 1

	def get_size(self, x):
		return self.rank[self.find(x)]

def solve():
	s = list(re())
	ans = 1000000000000.0
	for i in range(60):
		targ = str(1 << i)
		cnt = 0
		j = 0
		tmp = s.copy()
		while j < len(tmp):
			if j < len(targ) and tmp[j] == targ[j]:
				j += 1
			else:
				tmp.pop(j)
				cnt += 1
		ans = min(ans, cnt + (len(targ) - len(tmp)))
	print(ans)
	return
test(int(re()))


import sys
input = sys.stdin.readline
a = []
i = 1
while i < 10 ** 20:
	a.append(i)
	i *= 2
t = int(input())
for _ in range(t):
	n = int(input())
	s = str(n)
	l = len(s)
	an = float('inf')
	for i in a:
		ss = str(i)
		ll = len(ss)
		k = 0
		for j in s:
			if k >= ll:
				break
			if j == ss[k]:
				k += 1
		an = min(an, l + ll - 2 * k)
	print(an)


t = int(input())
while t > 0:
	t -= 1
	ans = 19260817
	n = int(input())
	now = str(n)
	lenn = len(now)
	for i in range(0, 61):
		p = str(int(pow(2, i)))
		leng = len(p)
		it = 0
		ansp = 0
		cnt = 0
		j = 0
		for j in range(0, lenn):
			if it < leng and now[j] == p[it]:
				cnt += 1
				it += 1
			else:
				ansp += 1
		if ansp + leng - cnt <= ans:
			ans = leng - cnt + ansp
	print(ans)


from sys import stdin, stdout
(input, print) = (stdin.readline, stdout.write)
from math import *

def main():
	for _ in range(int(input())):
		k = list(input())
		n = len(k)
		ans = 100
		for i in range(100):
			a = str(2 ** i)
			now = 0
			s = len(a)
			for r in range(n):
				if k[r] == a[now]:
					now += 1
				if now == s:
					break
			if ans > s - now + n - now:
				ans = s - now + n - now
		print(str(ans - 1) + '\n')
main()


import sys
from math import sqrt
r = [str(2 ** i) for i in range(100)]
input = sys.stdin.readline
t = int(input())
while t > 0:
	n = input().strip()
	ans = 1 << 30
	for i in r:
		c = 0
		for j in n:
			if c < len(i) and j == i[c]:
				c += 1
		ans = min(ans, len(i) - c + len(n) - c)
	print(ans)
	t -= 1


def dif(x, y):
	ans = 0
	r = 0
	for i in range(len(y)):
		p = x.find(y[i], r)
		if p == -1:
			return int(ans + len(x) - r + len(y) - i)
		ans = ans + p - r
		r = p + 1
	ans = ans + len(x) - r
	return ans
t = int(input())
while t:
	t = t - 1
	n = input()
	ans = 2147483647
	i = 1
	while i < 2 ** 63:
		ans = min(ans, dif(n, str(i)))
		i = i * 2
	ans = min(ans, dif(str(2 ** 63), n))
	print(ans)


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

def si():
	return input()

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

def msi():
	return map(str, input().split())

def li():
	return list(mi())
t = ii()
for _ in range(t):
	s = si()
	ans = 70
	for i in range(60):
		res = str(2 ** i)
		(i, j) = (0, 0)
		while i < len(s) and j < len(res):
			if s[i] == res[j]:
				j += 1
			i += 1
		ans = min(ans, len(s) + len(res) - 2 * j)
	print(ans)


import sys
try:
	sys.stdin = open('inputf.in', 'r')
	sys.stdout = open('outputf.in', 'w')
except:
	pass
import math
import sys
from math import sqrt
from collections import defaultdict
from collections import Counter
import string
from collections import deque
from functools import cmp_to_key
import bisect
from collections import OrderedDict
import heapq as hq
from queue import PriorityQueue
MOD = 10 ** 9 + 7

def ii():
	return int(sys.stdin.readline().strip())

def si():
	return sys.stdin.readline().strip()

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

def lsi():
	return list(map(str, sys.stdin.readline().strip().split()))

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

def dparr(m, n):
	return [[0] * n for i in range(m)]

def helper(s1, s2):
	i = 0
	j = 0
	cnt = 0
	while i < len(s1) and j < len(s2):
		if s1[i] == s2[j]:
			i += 1
			j += 1
		else:
			cnt += 1
			i += 1
	if i < len(s1):
		cnt += len(s1) - i
	if j < len(s2):
		cnt += len(s2) - j
	return cnt
t = ii()
sq = []
sqi = 0
while True:
	x = 2 ** sqi
	sq.append(str(x))
	if x > 10 ** 18:
		break
	sqi += 1
for _ in range(t):
	n = si()
	ans = float('inf')
	for nn in sq:
		ans = min(ans, helper(n, nn))
	print(ans)


def mapper(s):
	return [ord(c) - ord('0') for c in s]
pow2 = [1 << i for i in range(62)]
pow2s = [mapper(str(n)) for n in pow2]

def solve(A, B):
	m = len(B)
	matches = 0
	j = 0
	for a in A:
		while j < m and B[j] != a:
			j += 1
		if j >= m:
			matches -= 1
		else:
			matches += 1
		j += 1
	return m - matches
t = int(input())
for _ in range(t):
	n = int(input())
	ns = mapper(str(n))
	result = float('inf')
	for p in pow2s:
		val = solve(p, ns)
		result = min(result, val)
	print(result)


import collections
t = int(input())
cur = 1
pos = []
while cur <= 10 ** 30:
	pos.append(str(cur))
	cur *= 2
for case in range(t):
	k = input()
	res = float('inf')
	for x in pos:
		i = 0
		j = 0
		while i < len(x):
			while j < len(k) and i < len(x):
				if x[i] == k[j]:
					i += 1
				j += 1
			if j == len(k):
				break
		cur = len(x) - i + len(k) - i
		res = min(res, cur)
	print(res)


T = int(input())
for _ in range(T):
	s = input()
	ans = 64
	for i in range(60):
		t = str(1 << i)
		saved = 0
		k = 0
		while saved < len(t) and k < len(s):
			if t[saved] == s[k]:
				saved += 1
			k += 1
		ans = min(ans, len(s) + len(t) - 2 * saved)
	print(ans)


import sys
input = sys.stdin.readline
changes_needed = {}
for i in range(64):
	pot = str(2 ** i)
	j = 0
	for j in range(len(pot)):
		prefix = pot[:len(pot) - j]
		changes_needed[prefix] = min(changes_needed.get(prefix, 10000), j)

def make_a_power_of_two(n):
	best = len(n) + 1
	for p in range(len(n)):
		best = min(best, min_changes(n[p], n, p + 1))
	return best

def min_changes(prefix, n, pos):
	best = changes_needed.get(prefix, 1000) + len(n) - len(prefix)
	if best >= 1000:
		return best
	for p in range(pos, len(n)):
		best = min(best, min_changes(prefix + n[p], n, p + 1))
	return best
for _ in range(int(input())):
	n = input()[:-1]
	sys.stdout.write(f'{make_a_power_of_two(n)}\n')


t = int(input())

def lcs(A, B):
	n = len(B)
	L = 0
	for i in range(n):
		w = A.find(B[i])
		if w < 0:
			return L
		L += 1
		A = A[w + 1:]
	return L
for i in range(t):
	n = int(input())
	res = 10
	j = 0
	temp = 1
	while True:
		a = str(n)
		b = str(temp)
		S = len(a) + len(b) - 2 * lcs(a, b)
		res = min(res, S)
		temp = temp * 2
		if len(a) * 2 < len(b) or res == 0:
			break
		if temp > n and res <= 1:
			break
	print(res)


k = {}
a = 1
while a <= 10 ** 20:
	k[str(a)] = 0
	a *= 2

def result(b):
	ans = 99999999
	for i in k:
		q = b
		error = 0
		for j in range(len(i)):
			if i[j] in q:
				ind = q.index(i[j])
				error += ind
				q = q[ind + 1:]
			else:
				error += len(i) - j
				error += len(q)
				q = ''
				break
		if q:
			error += len(q)
		ans = min(ans, error)
	return ans
for i in range(int(input())):
	b = input()
	print(result(b))


po2s = [str(1 << i) for i in range(200)]

def matchActionCount(a, b):
	(i, j) = (0, 0)
	a_len = len(a)
	b_len = len(b)
	while i < a_len and j < b_len:
		if a[i] == b[j]:
			j += 1
		i += 1
	return b_len + a_len - 2 * j
for _ in range(int(input())):
	n = input().strip()
	result = min([matchActionCount(n, po2) for po2 in po2s])
	result = min(len(n) + 1, result)
	print(result)


t = int(input())
for i in range(0, t):
	n = int(input())
	maxi = 1000000000
	k = 1
	while k < 10 ** 16:
		maxi = min(maxi, len(str(n)) + len(str(k)))
		h1 = str(k)
		h2 = str(n)
		q = True
		s = 0
		while q:
			q = False
			for g in range(0, min(len(h1), len(h2))):
				if h1[g] != h2[g]:
					q = True
					s += 1
					r = ''
					for j in range(0, len(h2)):
						if j != g:
							r += h2[j]
					h2 = r
					break
		s += abs(len(h2) - len(h1))
		maxi = min(maxi, s)
		k *= 2
	print(maxi)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if True else 1):
	n = input()
	ans = len(n) + 1
	cur = 1
	while cur <= 10 ** 20:
		x = str(cur)
		j = 0
		for i in n:
			if i == x[j]:
				j += 1
				if j == len(x):
					break
		ans = min(ans, len(n) - j + len(x) - j)
		cur *= 2
	print(ans)


l = [str(2 ** i) for i in range(60)]

def f(x, s):
	c = 0
	it = 0
	for i in x:
		if i == s[it]:
			it += 1
			c += 1
			if it == len(s):
				break
	return len(x) - c + len(s) - c
for _ in range(int(input())):
	n = int(input())
	ans = 100
	n = str(n)
	for i in l:
		ans = min(ans, f(n, i))
	print(ans)


import time
from collections import deque

def inpt():
	return int(input())

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

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

def lcs(X, Y):
	m = len(X)
	n = len(Y)
	LCSuff = [[0 for i in range(n + 1)] for j in range(m + 1)]
	length = 0
	(row, col) = (0, 0)
	for i in range(m + 1):
		for j in range(n + 1):
			if i == 0 or j == 0:
				LCSuff[i][j] = 0
			elif X[i - 1] == Y[j - 1]:
				LCSuff[i][j] = LCSuff[i - 1][j - 1] + 1
				if length < LCSuff[i][j]:
					length = LCSuff[i][j]
					row = i
					col = j
			else:
				LCSuff[i][j] = 0
	resultStr = ['0'] * length
	while LCSuff[row][col] != 0:
		length -= 1
		resultStr[length] = X[row - 1]
		row -= 1
		col -= 1
	return ''.join(resultStr)

def solve():
	n = input()
	l = []
	for i in range(100):
		l.append(str(2 ** i))
	ans = len(n) + 1
	for i in range(100):
		j = 0
		length = 0
		latest = 0
		while j < len(n):
			if length < len(l[i]) and l[i][length] == n[j]:
				length += 1
				latest = j
			j += 1
		ans = min(ans, len(n) + len(l[i]) - 2 * length)
	print(ans)

def main():
	m = 10 ** 9 + 7
	t = int(input())
	while t:
		t -= 1
		solve()
main()


import os
import sys
import math
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def check(x, s):
	cnt = 0
	xx = list(x)
	ss = list(s)
	ind = 0
	for a in range(len(ss)):
		if ind >= len(xx):
			cnt += len(ss) - a
			break
		elif ss[a] != xx[ind]:
			cnt += 1
		else:
			ind += 1
	cnt += len(xx) - ind
	return cnt
l = [str(2 ** x) for x in range(80)]

def prog_name():
	n = int(input())
	if n & n - 1 == 0:
		print(0)
	else:
		s = str(n)
		m = 1000000
		for x in l:
			m = min(m, check(x, s))
		print(m)

def main():
	T = int(input())
	for unique in range(T):
		prog_name()
main()


import sys
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

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

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()

def li():
	return [int(i) for i in input().split()]

def lli(rows):
	return [li() for _ in range(rows)]

def si():
	return input()

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

def ins():
	return input().split()
pow2 = []
for i in range(63):
	pow2.append(str(1 << i))

def get(s1, s2):
	j = 0
	for i in range(len(s1)):
		if s1[i] == s2[j]:
			j += 1
		if j == len(s2):
			break
	return j
t = II()
for _ in range(t):
	n = II()
	num = str(n)
	ans = sys.maxsize
	for i in range(63):
		ans = min(ans, len(num) + len(pow2[i]) - 2 * get(num, pow2[i]))
	print(ans)


t = int(input())
Min = 9
for tests in range(t):
	n = input()
	Min = 10
	for i in range(61):
		x = str(2 ** i)
		y = n
		count = 0
		Index = 0
		for j in range(len(y)):
			if Index < len(x) and y[j] == x[Index]:
				Index += 1
			else:
				count += 1
		count += len(x) - Index
		if count < Min:
			Min = count
	print(Min)


i = 1
st = []
while i <= 10 ** 20 + 1:
	st.append(str(i))
	i *= 2

def dfs(n):
	m = len(n) + 1
	for i in st:
		j = 0
		for g in n:
			if g == i[j]:
				j += 1
				if j == len(i):
					break
		m = min(m, len(i) + len(n) - 2 * j)
	return m
for i in range(int(input())):
	print(dfs(input()))


import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def go(dst, src):
	(src, dst) = (list(src), list(dst))
	src.reverse()
	dst.reverse()
	r = 0
	while len(src) > 0 and len(dst) > 0:
		if src[-1] == dst[-1]:
			src.pop()
			dst.pop()
		else:
			src.pop()
			r += 1
	return r + len(src) + len(dst)
P = [str(2 ** i) for i in range(70)]
T = int(input())
for _ in range(T):
	k = input()
	m = len(k) + 1
	for s in P:
		m = min(m, go(s, k))
	print(m)


def change(a, b):
	start = 0
	for (i, x) in enumerate(b):
		try:
			start = a.index(x, start) + 1
		except ValueError:
			return len(a) + len(b) - i * 2
	return len(a) - len(b)
pow2 = [str(2 ** i) for i in range(65)]
for _ in range(int(input())):
	n = input()
	print(min((change(n, x) for x in pow2)))


power = [str(2 ** i) for i in range(64)]

def solve():

	def fn(x, s):
		it = c = 0
		for i in x:
			if i == s[it]:
				it += 1
				c += 1
				if it == len(s):
					break
		return len(x) - c + len(s) - c
	n = input()
	ans = 100
	for i in power:
		ans = min(ans, fn(n, i))
	return ans
t = int(input())
while t:
	print(solve())
	t -= 1


sr = lambda : input()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
inf = 10 ** 18
mod = 998244353
test = ir()
tmp = 1
ans = []
for i in range(70):
	ans.append(tmp)
	tmp *= 2
for t in range(test):
	n = ir()
	N = str(n)
	len_n = len(N)
	tmp = len(N) + 1
	for num in ans:
		NUM = str(num)
		len_num = len(NUM)
		num_ind = 0
		for (i, c) in enumerate(N):
			if num_ind < len_num and NUM[num_ind] == c:
				num_ind += 1
		if len_num - num_ind == 0:
			tmp = min(tmp, len_n - len_num)
		else:
			ttmp = len_num - num_ind
			ttmp += len_n - num_ind
			tmp = min(tmp, ttmp)
	print(tmp)


def maxPrefix(s, t):
	count = 0
	for i in range(0, len(t)):
		if count == len(s):
			break
		if t[i] == s[count]:
			count = count + 1
	return count
for _ in range(int(input())):
	n = input()
	ans = 100
	for s in [str(2 ** x) for x in range(70)]:
		ans = min(ans, len(s) + len(n) - 2 * maxPrefix(s, n))
	print(ans)


import os, sys
from io import BytesIO, IOBase

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class dict(dict):

	def __missing__(self, key):
		return 0
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda dtype: dtype(input().strip())
inp_d = lambda dtype: [dtype(x) for x in input().split()]
inp_2d = lambda dtype, n: [inp(dtype) for _ in range(n)]
inp_2ds = lambda dtype, n: [inp_d(dtype) for _ in range(n)]
inp_enu = lambda dtype: [(i, x) for (i, x) in enumerate(inp_d(dtype))]
inp_enus = lambda dtype, n: [[i] + [inp_d(dtype)] for i in range(n)]
ceil1 = lambda a, b: (a + b - 1) // b
po = [1]
for i in range(1, 60):
	po.append(po[-1] << 1)
for _ in range(inp(int)):
	(n, ans) = (inp(str), float('inf'))
	for i in po:
		(tem, ix, take) = (0, 0, 0)
		for (j, num) in enumerate(str(i)):
			while ix < len(n):
				if n[ix] == num:
					take += 1
					break
				ix += 1
				tem += 1
			ix += 1
		val = len(str(i)) - take
		if val == 0:
			ans = min(ans, tem + (len(n) - ix))
		else:
			ans = min(ans, tem + val)
	print(ans)


def cal(x, num, xx):
	y = str(x)
	nm = str(num)
	cnt = 0
	br = str(num)
	gr = ''
	for z in range(len(y)):
		if z != len(y) - 1:
			if y[z] in br:
				c = br.index(y[z])
				cnt += c
				br = br[c + 1:]
			else:
				cnt += len(br) + 1
				br = ''
		elif y[z] in br:
			cnt += len(br) - 1
		else:
			cnt += len(br) + 1
		if cnt > xx:
			return cnt
	return cnt
arr = [2 ** x for x in range(100)]
for _ in range(int(input())):
	num = input()
	if int(num) in arr:
		print(0)
		continue
	ct = len(num) + 1
	for x in arr:
		p = cal(x, num, ct)
		if p < ct:
			ct = p
	print(ct)


import sys
input = sys.stdin.readline
final = []
bi = [str(2 ** i) for i in range(55)]

def solve(a, b):
	l = len(a)
	l2 = len(b)
	if l > 2 * l:
		return l + 1
	j = 0
	for el in a:
		if el == b[j]:
			j += 1
		if j == l2:
			break
	return min(l + 1, l - 2 * j + l2)
for _ in range(int(input())):
	a = input()
	final += [min([solve(a, x) for x in bi]) - 1]
for k in final:
	print(k)


import os, sys
import math
from io import BytesIO, IOBase
from collections import Counter
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
z = [2 ** i for i in range(60)]
for _ in range(int(input())):
	x = int(input())
	s = str(x)
	ans = len(s) + 1
	for t in z:
		num = str(t)
		tp = 0
		for j in range(len(s)):
			if tp < len(num):
				if s[j] == num[tp]:
					tp += 1
		ans = min(ans, len(s) - tp + len(num) - tp)
	print(ans)


ar = [1]
n = 1
while n * 2 <= 10 ** 19:
	ar.append(n * 2)
	n = n * 2
t = int(input())
for i in range(t):
	inp = input()
	mini = 100000000
	for item in ar:
		sample = str(item)
		linp = len(inp)
		lsample = len(sample)
		start = 0
		k = 0
		for i in range(lsample):
			while start < linp:
				if sample[i] == inp[start]:
					k += 1
					start += 1
					break
				start += 1
			else:
				break
		mini = min(mini, linp - k + lsample - k)
	print(mini)


t = int(input())
for tt in range(t):
	a = input()
	ans = 1000000000
	g = 1
	for i in range(64):
		s = str(g)
		p = 0
		for j in a:
			if p < len(s) and j == s[p]:
				p += 1
		cans = len(s) - p + len(a) - p
		ans = min(ans, cans)
		g *= 2
	print(ans)


t = int(input())
for _ in range(t):
	n = input()
	min_ops = float('+inf')
	for r in range(60):
		s = str(2 ** r)
		ops = 0
		(i, j) = (0, 0)
		while i < len(n) and j < len(s):
			if n[i] == s[j]:
				j += 1
			else:
				ops += 1
			i += 1
		ops += len(n) - i
		ops += len(s) - j
		min_ops = min(ops, min_ops)
	print(min_ops)


l = [1]
for j in range(1, 64):
	l.append(l[-1] * 2)
t = int(input())
for i in range(t):
	n = input()
	mini = []
	for j in l:
		val = str(j)
		count = 0
		for k in range(len(n)):
			if count < len(val) and n[k] == val[count]:
				count += 1
		not_matched = len(n) - count
		delete = len(val) - count
		mini.append(not_matched + delete)
	print(min(mini))


l = []

def pre():
	i = 0
	while i <= 65:
		l.append(str(2 ** i))
		i += 1

def calc(s, i):
	n = len(s)
	m = len(l[i])
	(x, y) = [0, 0]
	while x < n and y < m:
		if s[x] == l[i][y]:
			x += 1
			y += 1
			continue
		x += 1
	return y

def main():
	for _ in range(int(input())):
		n = int(input())
		s = str(n)
		ans = 10 ** 9 + 7
		i = 0
		while i < len(l):
			appnd = len(l[i]) - calc(s, i)
			sz = len(s) - len(l[i]) + 2 * appnd
			ans = min(ans, sz)
			i += 1
		print(ans)
pre()
main()


def solve():
	T = int(input())
	powers = [1]
	while powers[-1] < 100000000000000000000001:
		powers.append(powers[-1] << 1)
	for _ in range(T):
		num = input()
		optimal = None
		minimum = 10000000
		for power in powers:
			power = str(power)
			(i, j) = (0, 0)
			covered = 0
			while i < len(num) and j < len(power):
				if power[j] == num[i]:
					j += 1
					i += 1
					covered += 1
				else:
					i += 1
			unused = len(num) - j
			ans = unused + len(power) - covered
			if minimum > ans:
				minimum = ans
				optimal = power
		print(minimum)
solve()


t = int(input())
for tc in range(t):
	n = int(input())
	p2 = []
	for i in range(60):
		p2.append(1 << i)
	x = str(n)
	N = len(x)
	ans = 20
	for i in range(len(p2)):
		y = str(p2[i])
		l = 0
		r = 0
		cnt = 0
		while l < len(y) and r < N:
			if x[r] == y[l]:
				cnt += 1
				r += 1
				l += 1
			else:
				r += 1
		if cnt == N:
			ans = min(ans, len(y) - cnt)
		else:
			ans = min(ans, len(y) + N - 2 * cnt)
	print(ans)


import sys
zz = 1
sys.setrecursionlimit(10 ** 5)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def dadd(d, p, val):
	if p in d:
		d[p].append(val)
	else:
		d[p] = [val]

def gi():
	return [xx for xx in input().split()]

def gtc(tc, *ans):
	print('Case #' + str(tc) + ':', *ans)

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def bits(i, n):
	p = bin(i)[2:]
	return (n - len(p)) * '0' + p

def prec(a, pre):
	for i in a:
		pre.append(pre[-1] + i)
	pre.pop(0)

def YN(flag):
	print('YES' if flag else 'NO')

def si():
	return list(input().rstrip())

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

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = fi()
INF = 10 ** 18
uu = t
mod = 10 ** 9 + 7

def check(n, m):
	a = str(n)
	b = str(m)
	i = j = 0
	while i < len(a) and j < len(b):
		if a[i] == b[j]:
			j += 1
		i += 1
	return len(b) - 2 * j + len(a)
while t > 0:
	t -= 1
	n = fi()
	ans = 10 ** 18
	for i in range(60):
		ans = min(ans, check(n, 2 ** i))
	print(ans)


twos = ['1']
for i in range(60):
	twos.append(str(int(twos[-1]) * 2))
anss = []
t = int(input())
for _ in range(t):
	n = input()
	ans = len(n) + 1
	for two in twos:
		i = 0
		for c in n:
			if two[i] == c:
				i += 1
			if i >= len(two):
				break
		ans = min(ans, len(n) - i + len(two) - i)
	print(ans)


from sys import path_hooks, stdin, stdout
from collections import Counter, deque
import math
from copy import deepcopy
import random
import heapq
import sys
sys.setrecursionlimit(10 ** 5)

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

def strinput():
	return stdin.readline().strip()

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

def intinput():
	return int(stdin.readline().strip())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	ans = []
	for p in range(n + 1):
		if prime[p]:
			ans.append(p)
	return ans
coprime1 = {6: 100003, 5: 10007, 4: 1009, 3: 101, 2: 11, 1: 2, 7: 1000003, 8: 10000019, 9: 100000007}
coprime2 = {8: 10000169, 9: 100000049, 7: 1000033, 6: 100019, 5: 10009, 4: 1013, 3: 103, 2: 13, 1: 3}

def writ(ss):
	stdout.write(str(ss) + '\n')
mod = 10 ** 9 + 7

def sumn(n):
	return n * (n + 1) // 2

def lcs(text1, text2):
	dp = [[0] * (len(text1) + 1) for i in range(len(text2) + 1)]
	for i in range(1, len(text2) + 1):
		for j in range(1, len(text1) + 1):
			if text2[i - 1] == text1[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	return dp[-1][-1]

def overlap(s1, s2):
	p = 0
	m = len(s2)
	for i in range(len(s1)):
		if s1[i] == s2[p]:
			p += 1
			if p == m:
				return len(s1) - m
	return m - p + (len(s1) - p)

def overlap1(s1, s2):
	p = 0
	m = len(s2)
	aaa = 0
	for i in range(len(s1)):
		if s1[i] == s2[p]:
			p += 1
			if p == m:
				return len(s1) - m
		else:
			aaa = len(s1) - i + 1
			break
	return m - p + (len(s1) - p)
p2 = [str(2 ** i) for i in range(100)]
ss2 = 9999999999999
ss1 = 9999999999999
for test in range(intinput()):

	def solve():
		n = strinput()
		ans = 999999999
		for i in p2:
			ss2 = overlap(n, i)
			ss = min(ss1, ss2)
			ans = min(ans, ss)
		return ans
	print(solve())


from math import *
from sys import *
power = []
val = 1
for i in range(60):
	power.append(str(val))
	val *= 2
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	y = str(n)
	ans = maxsize
	for hello in range(60):
		x = power[hello]
		cnt = 0
		start = 0
		for i in range(len(x)):
			s = x[i]
			pos = -1
			for j in range(start, len(y)):
				if s == y[j]:
					pos = j
					break
			if pos == -1:
				break
			start = pos + 1
			cnt += 1
		val = len(y) - cnt + (len(x) - cnt)
		ans = min(ans, val)
	print(ans)


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07

def dfs(a, b, p, c):
	if a == b:
		return c
	for (i, j) in adj[a]:
		if i == p:
			continue
		temp = dfs(i, b, a, c + j)
		if dfs(i, b, a):
			mx = max(i, mx)
			return 1
	return tot
ans = [1]
for i in range(61):
	ans.append(ans[-1] * 2)

def hnbhai(tc):
	n = sa()
	mn = 10000
	for i in range(61):
		x = str(ans[i])
		tot = 0
		j = 0
		while j < len(n) and tot < len(x):
			if n[j] == x[tot]:
				tot += 1
			j += 1
		mn = min(mn, len(x) - tot + len(n) - tot)
	print(mn)
for _ in range(sb()):
	hnbhai(_ + 1)


import sys

def auf(x, cur_pow):
	(s1, s2) = (0, 0)
	for i in range(len(x)):
		if s2 >= len(cur_pow):
			break
		if x[i] == cur_pow[s2]:
			s2 += 1
	return len(x) + len(cur_pow) - 2 * s2
n = int(input())
pow_2 = [2 ** i for i in range(60) if 2 ** i < 10 ** 18]
for _ in range(n):
	cur = input()
	ans = []
	for j in pow_2:
		ans.append(auf(cur, str(j)))
	print(min(ans))


import sys
input = sys.stdin.readline
from pprint import pprint
INF = 1 << 63
issqrt = set()
for i in range(0, 1000000):
	issqrt.add(str(2 ** i))
	if 2 ** i > 10 ** 24:
		break

def do():
	n = int(input())
	s = str(n)
	sl = len(s)
	res = 10 ** 9
	if s in issqrt:
		print(0)
		return
	for candidate in issqrt:
		found = 0
		for i in range(len(s)):
			if s[i] == candidate[found]:
				found += 1
			if found == len(candidate):
				break
		need = 0
		need += sl - found
		need += len(candidate) - found
		res = min(res, need)
	print(res)
q = int(input())
for _ in range(q):
	do()


import sys
from bisect import bisect_right as lb
from collections import deque
from queue import PriorityQueue as pq
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7
a = []
for i in range(62):
	a.append(2 ** i)
for _ in range(ii()):
	n = list(ip())
	mx = 100000.0
	for i in range(62):
		x = list(str(a[i]))
		j = 0
		t = 0
		while j < len(n) and t < len(x):
			if n[j] == x[t]:
				t += 1
			j += 1
		mx = min(mx, len(x) + len(n) - 2 * t)
	print(mx)


import math

def main():
	maxNum = 1e+18
	arr = []
	p = 1
	while p <= maxNum:
		arr.append(str(p))
		p <<= 1
	m = len(arr)
	for __ in range(int(input())):
		num = list(str(int(input())))
		n = len(num)
		dp = [[-1] * m for __ in range(n)]
		for i in range(n):
			for j in range(m):
				longest = dp[i - 1][j]
				if longest + 1 < len(arr[j]) and arr[j][longest + 1] == num[i]:
					dp[i][j] = longest + 1
				else:
					dp[i][j] = dp[i - 1][j]
		bestJ = 0
		k = float('inf')
		for j in range(m):
			delCost = n - (dp[-1][j] + 1)
			addCost = len(arr[j]) - (dp[-1][j] + 1)
			k = min(k, delCost + addCost)
		print(k)
	return 0
main()


import math
t = int(input())
pow = []
for i in range(60):
	pow.append(2 ** i)
for _ in range(t):
	n = int(input())
	if n & n - 1 == 0:
		print(0)
		continue
	l = []
	k = len(str(n))
	n = str(n)
	for p in pow:
		p = str(p)
		j = 0
		d = 0
		i = 0
		while i < len(p):
			if j < k:
				if p[i] != n[j]:
					while j < k and p[i] != n[j]:
						j += 1
				if j < k and p[i] == n[j]:
					d += 1
				j += 1
			i += 1
		ans = k - d + len(p) - d
		l.append(ans)
	print(min(l))


def find_min(c, i):
	cx = 0
	for l in c:
		if l == i[cx]:
			cx += 1
		if cx == len(i):
			break
	return len(i) - cx + len(c) - cx
z = [str(2 ** i) for i in range(60)]
for _ in range(int(input())):
	c = input()
	print(min([find_min(c, i) for i in z]))


b = []
d = 1
k32 = 61
for i in range(k32):
	b.append([])
	dd = d
	j = 0
	while dd > 0:
		b[i].append(j)
		b[i][j] = dd % 10
		dd = dd // 10
		j += 1
	d *= 2
for i in range(k32):
	bi = len(b[i])
	for j in range(bi // 2):
		t = b[i][j]
		b[i][j] = b[i][bi - j - 1]
		b[i][bi - j - 1] = t
___t = int(input())
for t___ in range(___t):
	n = int(input())
	a = []
	nn = n
	j = 0
	while nn > 0:
		a.append(j)
		a[j] = nn % 10
		nn //= 10
		j += 1
	an = len(a)
	for j in range(an // 2):
		t = a[j]
		a[j] = a[an - j - 1]
		a[an - j - 1] = t
	k = 100
	for l in range(k32):
		i = 0
		j = 0
		bi = len(b[l])
		m = 0
		while i < an and j < bi:
			if b[l][j] == a[i]:
				m += 1
				j += 1
			i += 1
		kk = an - m + bi - m
		if kk < k:
			k = kk
	print(k)


def generate():
	result = []
	for i in range(60):
		result += [str(2 ** i)]
	return result
gen = []

def lcs(first, second):
	count = 0
	lni = len(second)
	for value in first:
		if count == lni:
			break
		if second[count] == value:
			count += 1
	return count

def solution():
	n = input()
	global gen
	if n == '1000000000':
		print('9')
		return
	mn = 18
	ln = len(n)
	for item in gen:
		lni = len(item)
		lv = lcs(n, item)
		rem = ln - lv
		add = lni - lv
		mn = min(mn, rem + add)
	print(mn)

def main():
	global gen
	gen = generate()
	n = int(input())
	for i in range(n):
		solution()
main()


import math, io, os, sys

def lcs(X, Y, m, n):
	if m == 0 or n == 0:
		return 0
	elif X[m - 1] == Y[n - 1]:
		return 1 + lcs(X, Y, m - 1, n - 1)
	else:
		return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n))

def lcs2(x, y):
	r = 0
	cx = 0
	cy = 0
	lenx = len(x)
	leny = len(y)
	while cx < lenx and cy < leny:
		if x[cx] == y[cy]:
			r += 1
			cx += 1
			cy += 1
		else:
			cx += 1
	return r
t = int(input())
r = []
c = 1
for i in range(70):
	r.append(str(c))
	c *= 2
for _ in range(t):
	n = input()
	mn = 99999
	for i in r:
		d = lcs2(n, i)
		a = len(n) - d + len(i) - d
		if a < mn:
			mn = a
	print(mn)


t = int(input())
powers = [str(2 ** i) for i in range(100)]
for _ in range(t):
	k = input()
	res = len(k) + 1
	for p in powers:
		if p == k:
			res = 0
			break
		else:
			i = j = 0
			while i < len(p) and j < len(k):
				if p[i] == k[j]:
					i += 1
				j += 1
			res = min(res, len(k) - i + len(p) - i)
	print(res)


power_list = [2 ** i for i in range(100)]
leading_dict = dict()
for num in power_list:
	power_two = str(num)
	len_two = len(power_two)
	for i in range(len(power_two) + 1):
		prefix = power_two[:len_two - i]
		if prefix in leading_dict:
			if leading_dict[prefix] > i:
				leading_dict[prefix] = i
		else:
			leading_dict[prefix] = i
n = int(input())
for i in range(n):
	k = int(input())
	original_str = str(k)
	len_str = len(original_str)
	min_cost = len_str + leading_dict['']
	candidates = ['']
	vis = set([''])
	for i in range(len_str):
		new_candidates = []
		for candidate in candidates:
			new_candidate = candidate + original_str[i]
			if new_candidate in leading_dict:
				cost = len_str - len(new_candidate) + leading_dict[new_candidate]
				if cost < min_cost:
					min_cost = cost
			if new_candidate not in vis:
				new_candidates.append(new_candidate)
				vis.add(new_candidate)
		candidates = candidates + new_candidates
	print(min_cost)


def f(n, x):
	pn = 0
	px = 0
	taken = 0
	n = list(str(n))
	x = list(str(x))
	while pn < len(n) and px < len(x):
		if n[pn] == x[px]:
			taken += 1
			pn += 1
			px += 1
		else:
			pn += 1
	return len(n) + len(x) - 2 * taken
t = int(input())
a = []
for v in range(61):
	a += [2 ** v]
while t:
	n = int(input())
	mn = 30
	for x in a:
		if f(n, x) < mn:
			mn = f(n, x)
	print(mn)
	t -= 1


t = int(input())
kouho = []
for i in range(70):
	kouho.append(str(2 ** i))
for _ in range(t):
	n = str(input())
	ans = []
	for x in kouho:
		tmp = ''
		i = 0
		j = 0
		while i < len(x) and j < len(n):
			if x[i] != n[j]:
				j += 1
			else:
				tmp += x[i]
				i += 1
				j += 1
		ans.append(len(n) - len(tmp) + (len(x) - len(tmp)))
	print(min(ans))