题目描述

给一个数字 $N$，及 $K（1 \leq N \leq10^{15},2 \leq k \leq 1000)$ 给从 $0$ 到数字 $N$，有多少个数，它在 $K$ 进制下的表示方式 与在 $-K$ 进制下的表示是一样的。

输入格式

输出格式

21 3
21 2

9
8

提示

在第一个样例中有 $0\ 1\ 2\ 9\ 10\ 11\ 18\ 19\ 20$ 这九个数