题目描述

在一片古老的遗迹中，探险队发现了一座尘封的石门，石门上刻有一串由数字组成的神秘密码。据碑文记载，只有输入正确的密码，才能开启通往宝藏的通道。 密码的验证方式如下：

1. 从倒数第二位开始从右往左，每隔一个数位就将其乘 2，否则保留原数位不变。

2.将被乘 2 的数位分别计算其数位之和。

3.计算经过操作之后的所有数位之和，并将其乘 9 再对 10 取模，检验其是否等于最后一位（即校验位）。 例如，密码为 79927398713 时，验证过程如下：

将得到的和 67 乘 9 再对 10 取模，得到 67 × 9 mod 10 = 3。其中 3 为校验位，密码验证通过，石门缓缓开启。 现在，探险队发现了一段残缺的密码，其中缺失了一个数字，用符号 x 表示。你的任务是补全这个缺失的数字，使得密码能够通过验证，打开遗迹之门。

输入格式

第一行输入整数 𝑁，表示密码的长度。 第二行有一个长度为 𝑁 的字符串，表示密码。该字符串中只包含数字 0 ∼ 9 和字符 x。字符 x 将且仅将出现一次，表示缺失的数字。

输出格式

输出符合题意的数字。如果有多个可能的数字，输出最小的一个。

输入样例 1

11
7992739871x

输出样例 1

3

输入样例 2

5
x2464

输出样例 2

5

输入样例 3

10
93380x1696

输出样例 3

1

说明/提示

数据规模与约定

• 对于 50% 的数据，缺失的数字位于校验位，即 x 在字符串最后一位。

• 对于 100% 的数据，1 ≤ 𝑁 ≤ 100。