Alice and Bob are playing a game. The rule is as follows:

1. Initially, they are given a string consisted of digits '0' '9' and question marks ('?'). And the string contains at least one question mark.

2. Each player takes turn alternately. If the number of question marks is odd, the turns start with Alice. Otherwise, the turns start with Bob.

3. In each turn, the player can choose one of the question marks and change it to any digits ('0' '9') he/she likes.

4. The game ends when all question marks are changed to digits.

5. Assume the number represented by the final string is x. If x is a multiple of 11, the final score of this game is x. Otherwise, the final score of this game is -x.

Alice hopes the final score of this game is as large as possible, but Bob hopes the final score is as small as possible. Assume they both play the game with the best strategy, what's the final score of this game?

The first line contains one integer t () --- the number of test cases.

There are two lines in each test. The first line contains one integer n, indicating the length of the initial string in this game. The second line contains a string with length n --- the initial string of this game. The initial string consists of digits '0'  '9' and '?'. There is at least one question mark in the initial string.

The sum of n across the test cases doesn't exceed .

For each test, you should output one line contains the final score of this game if both Alice and Bob play with the best strategy. 

Notice that you may need to add leading zeroes such that the length of the digits part is exactly n. And if the answer is equal to zero, you cannot add the negative sign in front of the digits.

3
4
010?
2
??
4
0?0?

-0100
00
-0100

If you output -100 for the first test, you will get WA.

If you output either 0 or -00 for the second test, you will also get WA.