小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。

来源

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

市赛 进制转换

市赛进制转换