Problem 3A. 数圈圈

时间限制：1000ms

空间限制：256MB

题目描述

小添在纸上写下了一个数字k进制的数，10进制下对应的数为n。小添写下了这个数字后好奇这个数字里有多少个圈圈。具体来说是这样的，如‘0’有一个圈，‘B’有两个圈等等（大于10进制统一用大写字母）。

小添想让你统计一下这个k进制数有一共有多少个圈圈（不考虑前导零）。

输入格式

一行两个整数k和n。

输出格式

一个整数，表示一共有多少个圈。

样例输入1

10 80

样例输出1

3

数据范围及约定

对于100%的数据 \(0 \le n \le 10^{18}，2 \le k \le 16\)。

提示

数字	圈的个数
0	1
1	0
2	0
3	0
4	1
5	0
6	1
7	0
8	2
9	1
A	1
B	2
C	0
D	1
E	0
F	0