乘法

题目信息

时间限制: 1s

空间限制: 512M

输入文件: multi.in

输出文件: multi.out

题目描述

称一个非负整数在 $B$ 进制下是独特的，当且仅当它在 $B$ 进制下各位数字互不相同（正整数忽略前导 $0$，而 $0$ 本身是独特的）。例如在 $10$ 进制下，$114$ 不是独特的，但 $514$ 是独特的。在 $4$ 进制下 $114=(1302)_{(4)}$ 是独特的。容易发现，对于特定的 $B$，独特的数的数量是有限的。

输入 $n,B$，你需要求出 $B$ 进制下 $n$ 的所有非负整数倍数中，第二大的独特数是多少。如果不存在第二大，输出 $-1$。

输入格式

输入文件名为 multi.in。

第一行一个整数 $n$，第二行一个整数 $B$。

输出格式

输出文件名为 multi.out。

一行一个整数表示答案。用十进制输出。

样例

样例输入 1

2 2

样例输出 1

0

样例解释 1

$2$ 进制下所有独特数为：$10_{(2)}, 1_{(2)}, 0_{(2)}$，也就是 $2,1,0$。其中，是 $2$ 的倍数的是 $2,0$，第二大的是 $0$。

样例输入 2

9 6

样例输出 2

44505

样例解释 2

$6$ 进制下，$9$ 的倍数中最大的独特数是 $44550=542130_{(6)}$，第二大的是 $44505=542013_{(6)}$。

样例输入 3

3 2

样例输出 3

-1

样例解释 3

$2$ 进制下，是 $3$ 的倍数的独特数有且仅有 $0$，所以不存在第二大的。

更多样例

见附加文件。

数据范围与提示

对于所有数据，$1\le n\le 10^{18}, 2\le B\le 12$。