Description

There is an algorithm to check whether a certain bank card number is valid:

1. Starting from the second-to-last digit, move from right to left. Multiply every other digit by $2$; keep the remaining digits unchanged.
2. For each digit that was multiplied by $2$, compute the sum of its digits.
3. Compute the sum of all digits after the above operations, then multiply it by $9$ and take modulo $10$. Check whether the result equals the last digit (i.e., the check digit of the bank card number).

If the card number to be verified is $79927398713$, the checking process is as follows:

Multiply the obtained sum $67$ by $9$ and take modulo $10$, getting $67 \times 9 \bmod 10=3$. Here $3$ is the check digit of this card number, so the original card number is valid.

Now you are given a bank card number with one digit missing. According to the algorithm above, fill in a suitable digit at the missing position so that the resulting card number is valid.

Input Format

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

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

Output Format

Output a digit that satisfies the requirement. If there are multiple valid digits, output the smallest one.

11
7992739871x

3

5
x2464

5

10
93380x1696

1

Hint

Constraints

For $50\%$ of the testdata, 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 testdata, $1 \le N \le 100$.

Notes

The scoring of this problem follows the original COCI problem, with a full score of $50$.

Translated from COCI2018-2019 CONTEST #6 T1 Lun.

Translated by ChatGPT 5