合体（unite）

• 题目 PID：NC26JC
• 时间限制：1 秒
• 内存限制：512 MiB

问题背景

赛罗和迪迦为了对抗宇宙大 boss 贝坦杰亚，他们必须暂时放弃选票之争，联手合作。

问题描述

赛罗和迪迦各自都有必杀光线技能，并且都可以根据实际情况，在一定范围内调节光线的强度。具体说，赛罗可以在 $[l_1,r_1]$ 范围内任选一个正整数作为光线强度；迪迦可以在 $[l_2,r_2]$ 范围内任选一个正整数作为光线强度。

贝坦杰亚十分厉害，靠任何一个凹凸曼单独的力量无法打败，必须联合两者的必杀光线，形成集束光线。通过研究，仅当两者光线强度的乘积是完全平方数的时候，才能融合出集束光线。一个正整数 $x$ 是完全平方数，当且仅当存在一个正整数 $r$，使 $x=r^2$。

求赛罗和迪迦在各自强度范围内，有几种选择方案能融合出集束光线？两种方案不同当且仅当赛罗和迪迦至少有一个的光线强度不同。

形式化地，求有几组不同的二元组 $(A,B)$，使 $A,B$ 均为正整数，$A\in[l_1,r_1]$，$B\in[l_2,r_2]$，且 $A\times B$ 是完全平方数。

输入格式

从文件 unite.in 中读取数据。

一行 4 个正整数 $l_1,r_1,l_2,r_2$。

输出格式

输出到文件 unite.out。

一个整数表示答案。

文件读写示例

freopen("unite.in", "r", stdin);
freopen("unite.out", "w", stdout);

样例 1

1 10 1 10

18

样例 1 说明

满足条件的 $(A,B)$ 有：$(1,1),(1,4),(1,9),(2,2),(2,8),(3,3),(4,1),(4,4),(4,9),(5,5),(6,6),(7,7),(8,2),(8,8),(9,1),(9,4),(9,9),(10,10)$。

数据规模与约定

• 对于 $20\%$ 的数据，$r_1,r_2\leq5000$。
• 对于 $60\%$ 的数据，$r_1,r_2\leq200000$。
• 对于 $90\%$ 的数据，$r_1,r_2\leq2\times10^6$。
• 对于 $100\%$ 的数据，$1\leq l_1\leq r_1\leq2\times10^7$，$1\leq l_2\leq r_2\leq2\times10^7$。

提示：注意空间开销。