_If you want to practice topicwise questions in the ladder way like a2oj , do register on my site *http://codedigger.tech* after the contest. Here you will get Handpicked Topicwise Questions from codeforces, codechef, uva and spoj for your better practice. Best of Luck._
Chitra is playing with consecutive numbers from $n$ to $m$ $(3 <= n + 2 <= m <= 10^9)$. Singhal tells her that the contest of Number Theory is over and concatenates all the numbers to a String But he miss *one number* from anywhere in the middle to concatenate.
Example — If she is playing with numbers from $3$ to $7$. He can concatenates this in the following way - $3567$ missing $4$ or other possibility would be $3467$, $3457$, but not $4567$, $3456$ , $367$ , $357$.
He gave back this concatenated string to her. Help her in finding the missing number. If there are many solution to this, you have to find the minimum possible.
*Note: It is guaranteed that a solution smaller than $10^9$ must exists in the given inputs.*
The first line contains a single integer $t (1 <= t <= 10^5)$ — the number of test cases in the input. Then $t$ test cases follow.
Each query contains a single concatenated string $S (1 <= | S | <= 10^5)$. $| S |$ is the length of the string.
It is guaranteed that the total sum of $| S |$ is at most $10^5$.
For each test from the input print the missing number $< 10^9$. Print the answers to the tests in the order in which the tests are given in the input.
In the first query - the string S = _13_, then the sequence is $1$, $3$ and the missing number is $2$.
In the second query - the string S = _3457_, then the sequence is $3$, $4$, $5$, $7$ and the missing number is $6$.
In the third query - the string S = _1314151718_, then the sequence is $13$, $14$, $15$, $17$, $18$ and the missing number is $16$.
In the last query - the string S = _234235236238_, then the sequence is $234$, $235$, $236$, $238$ and the missing number is $237$.
## Input
The first line contains a single integer $t (1 <= t <= 10^5)$ — the number of test cases in the input. Then $t$ test cases follow.Each query contains a single concatenated string $S (1 <= | S | <= 10^5)$. $| S |$ is the length of the string.It is guaranteed that the total sum of $| S |$ is at most $10^5$.
## Output
For each test from the input print the missing number $< 10^9$. Print the answers to the tests in the order in which the tests are given in the input.
[samples]
## Note
In the first query - the string S = _13_, then the sequence is $1$, $3$ and the missing number is $2$.In the second query - the string S = _3457_, then the sequence is $3$, $4$, $5$, $7$ and the missing number is $6$.In the third query - the string S = _1314151718_, then the sequence is $13$, $14$, $15$, $17$, $18$ and the missing number is $16$.In the last query - the string S = _234235236238_, then the sequence is $234$, $235$, $236$, $238$ and the missing number is $237$.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ n_k \in \mathbb{Z} $ be the number of students.
- Let $ p_k \in \mathbb{Z} $ be the passing threshold percentage ($ 1 \leq p_k \leq 100 $).
- For each student $ i \in \{1, \dots, n_k\} $, define two scores: $ a_{k,i}, b_{k,i} \in \mathbb{Z} $ with $ b_{k,i} \leq a_{k,i} $.
**Constraints**
1. $ 1 \leq T \leq 5 \times 10^3 $
2. $ 1 \leq n_k \leq 2 \times 10^5 $ for each $ k $
3. $ 1 \leq b_{k,i} \leq a_{k,i} \leq 10^9 $ for all $ i, k $
4. $ \sum_{k=1}^T n_k \leq 5 \times 10^5 $
**Objective**
For each test case $ k $, determine the maximum number of students that can pass under any assignment of mindsets (i.e., for each student $ i $, choose either $ a_{k,i} $ or $ b_{k,i} $ as their score), such that:
- Let $ x $ be the maximum score among all students in that assignment.
- A student passes if their score $ \geq \left\lceil x \cdot \frac{p_k}{100} \right\rceil $.
- Maximize the number of passing students over all possible assignments.