407331: GYM102766 E Singhal and Missing Number

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\le n+2 \le m \le 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 \le t \le 10^5)$$$ — the number of test cases in the input. Then $$$t$$$ test cases follow.

Each query contains a single concatenated string $$$S (1\le |S| \le 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.

4
13
3457
1314151718
234235236238

2
6
16
237

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$$$.