Binary Decimal
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.
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.
For each test case, output the smallest number of binary decimals required to represent $n$ as a sum.
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.
3
121
5
1000000000
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$.