该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

徐老师的进位结算

题目描述

徐老师的二次元商店使用 $B$ 进制货币。存在面额为 $1,B,B^2,B^3,\ldots$ 的硬币，每种硬币都有无限枚。

你要支付一个正整数金额 $N$。你可以先交出若干枚硬币，也可以多付；收银员随后用同样的硬币找零。交出和找回的硬币总数都计入代价。

金额 $N$ 以 $B$ 进制字符串给出。请计算完成结算所需的最少硬币总数。

输入格式

第一行输入一个整数 $B$。

第二行输入一个字符串 $N$，表示 $B$ 进制金额。

• $2 \le B \le 10$
• $1 \le |N| \le 10^6$
• $N$ 的每个字符都是 0 到 B-1
• $N$ 的首字符不是 0

输出格式

输出一个整数，表示交出和找回的硬币总数的最小值。

输入输出样例 #1

输入 #1

4
3

输出 #1

2

输入输出样例 #2

输入 #2

3
12

输出 #2

3

说明/提示

样例 1 中，可以交出一枚面额为 $4$ 的硬币，再找回一枚面额为 $1$ 的硬币，共使用 $2$ 枚。

样例 2 的金额为十进制的 $5$。可以交出两枚面额为 $3$ 的硬币，再找回一枚面额为 $1$ 的硬币，共使用 $3$ 枚。