Binary Decimal

1000ms

524288K

Description:

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.

Sample Input:

Sample 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, $$$1\,000\,000\,000$$$ is a binary decimal itself, thus the answer is $$$1$$$.

Informação

Provedor Codeforces

Código CF1530A