Background

常州市 2015“信息与未来”夏令营选拔赛

Description

小 $X$ 喜欢研究进制转换。

在了解了进制转换的一般流程后，小 $X$ 突然想起了以前学过的回文数（正着读倒着读都一样的数），于是开始思考一个奇怪的问题：$1$ 到 $N$ 中有多少个整数的平方在 $M$ 进制下是回文数呢？

小 $X$ 随手列了几个：

• $2$ 的平方 $4$，$10$ 进制表示为 $4$，是回文数
• $3$ 的平方$9$，$2$ 进制表示为 $1001$，是回文数
• $9046$ 的平方 $81830116$，$16$ 进制表示为$4E0A0E4$，是回文数。

小 $X$ 觉得要全列出来太难了，希望你帮帮他。

Format

Input

第一行包含用一个空格隔开的两个整数 $N,M$。

Output

第一行包含一个整数，表示满足要求的整数个数。

Samples

2 10

2

Limitation

对于 $30\%$ 的数据，$M=10$

对于另外 $30\%$ 的数据，$M=2$

对于 $100\%$ 的数据，$1≤N≤10000，2≤M≤16$