二进制转R进制

给定一个二进制数, 请把它转成R进制数输出.

Input

输入两行，第一行为一个二进制数，保证该二进制数转换十进制后为一个在int型范围内的非负整数。、

第二行为一个整数R，表示对应要转的R进制（2≤R≤32）

Output

一行一个结果，为转换后的R进制数。 请注意，R进制数中如包含字母，这里规定必须为大写

Examples

Input

11
10

Output

3

来源

lema
Time limit 1 second
Memory limit 128 MB
讨论 统计