题目描述

小X喜欢研究进制转换。

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

小X随手列了几个：

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

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

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

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

输入

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

输出

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

样例

2 10

2

说明

数据范围

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

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

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