A. Binary Decimaltime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard outputLet'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.InputThe 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.OutputFor each test case, output the smallest number of binary decimals required to represent n as a sum.ExampleInput
3
121
5
1000000000
Output
2
5
1
NoteIn 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, 1\,000\,000\,000 is a binary decimal itself, thus the answer is 1.
3
121
5
1000000000

2 5 1 
['greedy', 'math', '*800']