描述

小X喜欢研究进制转换。 在了解了进制转换的一般流程后，小 X 突然想起了以前学过的回文数（正着读倒着读都一样的数），于是开始思考一个奇怪的问题：$1$到$N$中有多少个整数的平方在$M$进制下是回文数呢？ 小X随手列了几个： $2$的平方$4$，$10$进制表示为$4$，是回文数； $3$的平方$9$，$2$进制表示为$1001$，是回文数； $9046$的平方$81830116$，$16$进制表示为$4E0A0E4$，是回文数。 小X觉得要全列出来太难了，希望你帮帮他。

输入

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

输出

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

样例

2 10

2

5000 16

18

数据范围:

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

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

对于 100% 的数据，1≤𝑁≤10000，2≤𝑀≤16。