Problem Description

There is an algorithm to determine the validity of a certain type of bank card number:

1. Starting from the second-to-last digit and moving left, every other digit is doubled. The other digits remain unchanged.
2. Calculate the sum of the digits for each doubled number.
3. Sum all the digits after the operations, multiply the result by 9, and then take the modulus of 10. Check if this value equals the last digit (the check digit of the bank card number).

For example, if the card number to be verified is $79927398713$, the steps are as follows:

Multiplying the sum $67$ by $9$ and taking the modulus of $10$ gives $67 \times 9 \bmod 10 = 3$. Since $3$ is the check digit of the card number, the original card number is valid.

Given a bank card number with one missing digit, use the above algorithm to fill in the missing digit such that the resulting card number is valid.

Input Format

The first line contains an integer $N$, the length of the bank card number with the missing digit.

The second line contains a string of length $N$, representing the bank card number. The string consists of digits $0$ to $9$ and the character x. The character x appears exactly once and represents the missing digit.

Output Format

Output the digit that makes the card number valid. If there are multiple valid digits, output the smallest one.

Sample Input and Output

Sample Input #1

11
7992739871x

Sample Output #1

3

Sample Input #2

5
x2464

Sample Output #2

5

Sample Input #3

10
93380x1696

Sample Output #3

1

Notes

Data Size and Constraints

For $50\%$ of the test cases, the missing digit is at the check digit position, i.e., the character x is at the last position of the string.

For $100\%$ of the test cases, $1 \le N \le 100$.

Notes

This problem is worth $50$ points as per the original COCI settings.

The problem is translated from COCI2018-2019 CONTEST #6 T1 Lun.

见题面 Input 部分

见题面 Output 部分