题目描述

小 X 喜欢研究进制转换。

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

小 X 随手列了几个：

2 的平方 4 ，10 进制表示为 4 ，是回文数；

3 的平方 9 ，2 进制表示为 1001，是回文数；

9046 的平方 81830116 , 16 进制表示为 4E0A0E4 ，是回文数。

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

输入格式

用一个空格隔开的两个整数 N , M 。

数据范围

对于 30% 的数据， M=10 。

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

对于 100%的数据，1 ≤ N ≤ 10000 , 2 ≤ M ≤ 16 。

输出格式

一个整数，表示满足要求的整数个数。

样例

2 10

2