给定一个十进制自然数的范围和进制的范围，十进制自然数范围在1~44700之间，进制的范围在2~36之间。给定范围里的数中，有些数的平方，在某进制下既是完全平方数又是回文数。本题的任务是统计给定范围内有多少个数的平方满足下列条件：仅在某一进制下既是完全平方数又是回文数。
说明：3^2=9，因为它在十进制和十一进制中都是回文数，所以9不能算；同样，26^2=676也不算。
输入
一行四个整数，分别表示给定的十进制自然数的范围和进制的范围。
输出
一行一个正整数，表示给定范围内满足条件的数的个数。
样例
输入
1 100 9 11
输出
12
提示
【样例说明】
6^2=36=33 base 11
10^2=100=121 base 9
11^2=121=121 base 10
12^2=144=121 base 11
20^2=400=484 base 9
22^2=484=484 base 10
24^2=576=484 base 11
72^2=5184=3993 base 11
82^2=6724=10201 base 9
84^2=7056=5335 base 11
91^2=8281=12321 base 9
100^2=10000=14641 base 9