Let's call a number a binary decimal if it's a positive integer and all digits in its decimal notation are either $0$ or $1$. For example, $1\,010\,111$ is a binary decimal, while $10\,201$ and $787\,788$ are not.

Given a number $n$, you are asked to represent $n$ as a sum of some (not necessarily distinct) binary decimals. Compute the smallest number of binary decimals required for that.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 1000$), denoting the number of test cases.

The only line of each test case contains a single integer $n$ ($1 \le n \le 10^9$), denoting the number to be represented.


-----Output-----

For each test case, output the smallest number of binary decimals required to represent $n$ as a sum.


-----Examples-----

Input
3
121
5
1000000000
Output
2
5
1


-----Note-----

In the first test case, $121$ can be represented as $121 = 110 + 11$ or $121 = 111 + 10$.

In the second test case, $5$ can be represented as $5 = 1 + 1 + 1 + 1 + 1$.

In the third test case, $1000000000$ is a binary decimal itself, thus the answer is $1$.

Difficulty: EASY
Tags: Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	print(max(map(int, list(input()))))


t = int(input())
lis = []
for i in range(t):
	sum = 1
	a = input()
	for i in a:
		if i != '0' and i != '1':
			if sum < int(i):
				sum = int(i)
	lis.append(sum)
for i in lis:
	print(i)


loop = int(input())
for k in range(loop):
	inp = input()
	if int(inp) == 0:
		print(1)
	else:
		print(int(max(inp)))


t = int(input())
for i in range(t):
	n = list(input())
	print(max(n))


def main() -> None:
	for t in range(int(input())):
		print(max(input()))
main()


for t in range(int(input())):
	n = str(input())
	count = 0
	for i in n:
		d = int(i)
		count = max(count, d)
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	s = str(n)
	result = 0
	for j in range(len(s)):
		a = int(s[j])
		if a > result:
			result = a
	print(result)


n = int(input())
for _ in range(n):
	s = input()
	mx = 1
	for i in s:
		if int(i) > mx:
			mx = int(i)
	print(mx)


def game():
	t = int(input())
	n = []
	while t < 1 or t > 1000:
		print('error donner t')
		t = int(input())
	for x in range(t):
		n.append(ask())
	k = 0
	while k < t:
		max = 0
		max = calcul(n, k)
		print(max)
		k = k + 1

def ask():
	b = int(input())
	while b < 1 or b > 1000000000:
		b = int(input())
	return b

def calcul(n, k):
	i = 0
	b = 0
	number_str = str(n[k])
	max = int(number_str[0])
	for c in number_str:
		d = int(c)
		if d > max:
			max = d
	return max
game()


def binary_decimal():
	a = int(input())
	for i in range(a):
		b = input()
		print(max(b))
binary_decimal()


t = int(input())
for _ in range(t):
	n = max(list(input()))
	print(n)


t = int(input())
for i in range(t):
	n = int(input())
	s = str(n)
	l = []
	for i in s:
		l.append(int(i))
	print(max(l))


t = int(input())
for _ in range(t):
	_max = max(list(map(int, input())))
	if _max > 1:
		print(_max)
	else:
		print(1)


n = int(input())
for i in range(n):
	s = [int(k) for k in input()]
	print(max(s))


for _ in range(int(input())):
	a = list((int(x) for x in input()))
	a.sort(reverse=True)
	print(a[0])


from collections import Counter, deque
from itertools import accumulate, product, groupby
import operator
import math
from functools import reduce

def solve():
	num = input()
	ip = [int(char) for char in num]
	return max(ip)
for _ in range(int(input())):
	print(solve())


for i in range(int(input())):
	n = input()
	ans = 0
	print(max(n))


for _ in range(int(input())):
	n = input()
	l = list(n)
	print(int(max(l), 10))


for _ in range(int(input())):
	print(max((i for i in str(input()))))


for _ in range(int(input())):
	print(max(input()))


for _ in range(int(input())):
	n = input()
	a = max(n)
	if a > '1':
		print(a)
	else:
		print(1)


for _ in range(int(input())):
	n = input()
	maxx = 0
	for i in n:
		maxx = max(maxx, int(i))
	print(maxx)


for i in range(int(input())):
	print(max(input()))


t = int(input())
for k in range(t):
	n = int(input())
	ans = 0
	while n > 0:
		ans = max(ans, n % 10)
		n //= 10
	print(ans)


n = int(input())
for i in range(n):
	x = input()
	max = 0
	for i in range(0, len(x)):
		if int(x[i]) - 0 > max:
			max = int(x[i]) - 0
	print(max)


for _ in range(int(input())):
	w = [int(i) for i in list(input())]
	print(max(w))


n = int(input())
for i in range(n):
	p = input()
	print(max(p))


n = int(input())
for i in range(0, n):
	print(max(list(map(int, list(input())))))


t = int(input())
r = ''
for _t in range(t):
	r += max([x for x in input()]) + '\n'
print(r)


for i in range(int(input())):
	x = list(map(int, input()))
	print(max(x))


for _ in range(int(input())):
	n = input()
	s = set()
	for i in n:
		s.add(int(i))
	print(max(s))


n = int(input())
for _ in range(n):
	k = list(map(int, input()))
	print(max(k))


n = int(input())
for i in range(n):
	num = input()
	li = list(map(int, num))
	print(max(li))


n = int(input())
arr = []
for i in range(n):
	k = int(input())
	arr.append(k)

def max_ele(ele):
	max = -1
	for k in str(ele):
		if int(k) > max:
			max = int(k)
	return max
for ele in arr:
	ans = max_ele(ele)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	max = -1
	while n != 0:
		if n % 10 > max:
			max = n % 10
		n = n // 10
	print(max)


test_cases = int(input())
for test_case in range(test_cases):
	print(max([int(c) for c in input()]))


for t in range(int(input())):
	n = input()
	l = [int(i) for i in n]
	ma = max(l)
	if ma == 0 or ma == 1:
		print('1')
	else:
		print(ma)


for i in range(int(input())):
	n = int(input())
	s = list(str(n))
	print(max(s))


def compute(x):
	res = 1
	while x != 0:
		res = max(res, x % 10)
		x = x // 10
	return res
n = int(input())
for _ in range(n):
	x = int(input())
	print(compute(x))


t = int(input())
for i in range(t):
	n = input()
	a = [char for char in n]
	ma = 0
	for i in range(len(a)):
		ma = max(ma, int(a[i]))
	print(ma)


T = int(input())
for case in range(T):
	s = input()
	arr = list(map(int, s))
	print(max(arr))


import sys

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

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

def get_num():
	return int(sys.stdin.readline())
t = get_num()
for i in range(t):
	n = get_num()
	a = []
	while n:
		a.append(n % 10)
		n = int(n / 10)
	print(max(a))


n = int(input())
a = []
for k in range(n):
	z = []
	m = input()
	for x in range(len(m)):
		z.append(int(m[x]))
	q = max(z)
	a.append(q)
for k in a:
	print(k)


for __ in range(int(input())):
	print(max(input()))


t = int(input())
while t:
	t = t - 1
	n = int(input())
	n = str(n)
	list1 = [int(i) for i in n]
	print(max(list1))


m = int(input())
l = []
for i in range(m):
	l.append(max(list(map(int, input()))))
for i in l:
	print(i)


t = int(input())
a = ['2', '3', '4', '5', '6', '7', '8', '9']
for inh in range(0, t):
	n = input()
	ans = 1
	for i in range(0, 8):
		if a[i] in n:
			ans = a[i]
	print(ans)


k = []
for _ in range(int(input())):
	s = input('')
	r = 0
	for i in range(len(s)):
		r = max(r, int(s[i]))
	k.append(r)
for i in k:
	print(i)


t = int(input())
for tests in range(0, t):
	n = int(input())
	max_num = 0
	while n != 0:
		rem = n % 10
		max_num = max(max_num, rem)
		n = n // 10
	print(max_num)


for _ in range(int(input())):
	n = int(input())
	print(max(map(int, str(n))))


def func():
	t = int(input())
	for _ in range(t):
		num = list(input().strip())
		print(max(num))
func()


def func(n):
	c = 1
	while n > 0:
		c = max(c, n % 10)
		n //= 10
	return c
t = int(input())
for i in range(t):
	n = int(input())
	print(func(n))


for _ in range(int(input())):
	n = input()
	a = [int(i) for i in n]
	print(max(a))


n = int(input(''))
for i in range(n):
	t = input('')
	d = 0
	for j in range(len(t)):
		d = max(d, int(t[j]))
	print(d)


t = int(input())
for ele in range(t):
	s = input()
	maxx = 0
	for i in s:
		if int(i) > maxx:
			maxx = int(i)
	print(maxx)


class Solution:

	def binDecimal(self, Num):
		cnt = 1
		for digit in Num:
			cnt = max(cnt, int(digit))
		return cnt
t = int(input())
s = Solution()
while t:
	Num = input()
	print(s.binDecimal(Num))
	t -= 1


t1 = int(input())
for _ in range(t1):
	s = str(input())
	a = list(map(int, s))
	print(max(a))


from cmath import *
from math import *
from decimal import *
from collections import *
import sys

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

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

def _int():
	return int(input())

def solves():
	s = input()
	print(max(s))
t = 1
t = int(input())
for _ in range(0, t):
	solves()


for i in range(int(input())):
	min_count = -1
	num = str(input())
	for j in range(len(num)):
		val = ord(num[j]) - ord('0')
		if val > min_count:
			min_count = val
	print(min_count)


for i in range(int(input())):
	n = int(input())
	m = str(n)
	highest = set()
	for j in range(len(m)):
		highest.add(int(m[j]))
	print(max(highest))


import sys
input = sys.stdin.readline

def solve():
	a = max(input())
	print(a)
for i in range(int(input())):
	solve()


def main():
	a = int(input())
	for i in range(a):
		print(max(list(map(int, input()))))
main()


n = int(input())
for i in range(n):
	s = input()
	mx = max(s)
	print(mx)


for _ in range(int(input())):
	n = int(input())
	mx = n % 10
	while n != 0:
		r = n % 10
		if r > mx:
			mx = r
		n = n // 10
	print(mx)


import sys
input = sys.stdin.readline

def main():
	t = int(input())
	for _ in range(t):
		n = input()[:-1]
		ans = 0
		for i in range(len(n)):
			ans = max(ans, int(n[i]))
		print(ans)
main()


for _ in range(int(input())):
	n = input()
	max = -1
	for i in n:
		if int(i) > max:
			max = int(i)
	print(max)


import os
import random
from sys import stdin, stdout
random.seed()

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

def read_int():
	return [int(i) for i in read().split()]

def write(s):
	stdout.write(s)
for _ in range(int(read())):
	print(max(list(read())))


for _ in range(int(input())):
	s = input()
	k = max(s)
	print(k)


def main():
	for _ in range(int(input())):
		k = list(input())
		d = max(k)
		print(ord(d) - ord('0'))
main()


t = int(input())
for i in range(t):
	n = int(input())
	w = []
	while n > 0:
		w.append(n % 10)
		n //= 10
	print(max(1, max(w)))


import sys
input = sys.stdin.readline

def solve(n):
	return max(list(map(int, n)))
for _ in range(int(input())):
	print(solve(input().strip()))


t = int(input())
while t > 0:
	n = int(input())
	ans = -1
	while n > 0:
		r = n % 10
		if r > ans:
			ans = r
		n = n // 10
	print(ans)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	n = list(str(n))
	p = max(n)
	print(p)


n = int(input())
for i in range(n):
	a = int(input())
	ans = 0
	while a:
		ans = max(ans, a % 10)
		a //= 10
	print(ans)


t = int(input())
for _ in range(t):
	n = input()
	s = set()
	for i in n:
		s.add(i)
	num = max(s)
	if num == 0:
		print(1)
	else:
		print(num)


t = int(input())
for case in range(t):
	x = int(input())
	maxDigit = 0
	while x > 0:
		maxDigit = max(maxDigit, x % 10)
		x = x // 10
	print(maxDigit)


t = int(input())
for T in range(t):
	n = int(input())
	m = 0
	while n > 0:
		c = n % 10
		if c > m:
			m = c
		n = n // 10
	print(m)


for _ in range(int(input())):
	s = list(str(input()))
	a = []
	for i in range(len(s)):
		a.append(int(s[i]))
	print(max(a))


d = int(input())
for p in range(0, d):
	n = input()
	c = max(n)
	print(int(c))


for _ in range(int(input())):
	s = input()
	for i in range(9, 0, -1):
		if str(i) in s:
			print(i)
			break


t = int(input())
while t != 0:
	s = input()
	n = len(s)
	mk = 0
	c = 0
	for i in range(n):
		if s[i] == '1' or s[i] == '0':
			c = 27
		else:
			m = int(s[i]) - 1
			if mk < m:
				mk = m
	print(mk + 1)
	t = t - 1