Problem R: 进制回文数

Problem R: 进制回文数

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MiB

Description

对于正整数 n,把它转换成k 进制(无前置 0),如果该 k 进制序列正读和反读完全一样,就称这个数是k 进制回文数。 给定两个整数 n,k,求 1~n 之间一共有多少个 k 进制回文数。

例如:n=15,k=2,就是原题,1‑15 中二进制回文数一共 6 个。

Input

一行两个整数 n,k

Output

输出一个整数:1~n 范围内 k 进制回文数的总个数。

Sample Input Copy

15 2

Sample Output Copy

6