G. Subsequence MEX II
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are a member of the Rutgers Programming Contest problemsetting team, and you have just come up with a new problem for the Spring 2025 contest. However, you realized you're not yet sure how to write the judge program for this problem. Your task now is to implement that judge.

Define a number $$$b$$$ to be a subsequence of a number $$$a$$$ if, when you write out $$$a$$$ in decimal notation, you can erase some (but not all) of its digits so that the remaining digits, in order, form $$$b$$$. For example, $$$356$$$ is a subsequence of $$$1234567$$$, because you can erase the $$$1$$$, $$$2$$$, $$$4$$$, and $$$7$$$ to form $$$356$$$. However, $$$0$$$ is not a subsequence of $$$23527$$$, because the digit $$$0$$$ is not present in $$$23527$$$.

The problem you have just come up with requires the user to construct an integer $$$n$$$ such that the $$$\operatorname{MEX}$$$ of its subsequences is the input number $$$x$$$. Therefore, the judge program should read an integer $$$n$$$ from the user and compute the $$$\operatorname{MEX}$$$ of its subsequences, so that value can then be compared against the original input $$$x$$$.

The $$$\operatorname{MEX}$$$ of a set of integers is defined as the smallest non-negative integer which does not occur in the set. For example, the $$$\operatorname{MEX}$$$ of $$$\{0, 1, 2, 4\}$$$ is $$$3$$$, and the $$$\operatorname{MEX}$$$ of $$$\{1, 4, 6, 8\}$$$ is $$$0$$$.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases.

Each test case consists of a single line containing an integer $$$n$$$ ($$$1 \le n \lt 10^{2\cdot 10^5}$$$) — the number chosen by the user's program. It is guaranteed that $$$n$$$ does not contain leading zeroes.

It is guaranteed that the total number of digits of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, print a single line containing one integer $$$x$$$ — the $$$\operatorname{MEX}$$$ of all subsequences of $$$n$$$.

Example
Input
6
123
70
12836880457
2468013579
12013456789
23609713987621002462058
Output
0
1
9
10
22
41
Note

In the first test case, $$$n=123$$$ does not contain $$$0$$$ as a subsequence, and therefore the $$$\operatorname{MEX}$$$ of its subsequences is $$$0$$$.

In the third test case, $$$n$$$ contains all digits except for $$$9$$$, making the $$$\operatorname{MEX}$$$ of its subsequences equal to $$$9$$$.