题目描述

给定十进制自然数范围和进制范围，统计有多少个数的平方在某一进制下既是完全平方数又是回文数，且仅在该进制下满足此条件。

输入格式

一行四个整数，分别表示十进制自然数的范围[a,b]和进制的范围[c,d]

输出格式

满足条件的数的个数

样例

输入 #1

1 100 9 11

输出 #1

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$