Nastya Studies Informatics【好多细节、好坑的题，或许是我太弱了吧，不过我找到了WA的原因了】

Today on Informatics class Nastya learned about GCD and LCM (see links below). Nastya is very intelligent, so she solved all the tasks momentarily and now suggests you to solve one of them as well.

We define a pair of integers (a, b) good, if GCD(a, b) = x and LCM(a, b) = y, where GCD(a, b) denotes the greatest common divisor of a and b, and LCM(a, b) denotes the least common multiple of a and b.

You are given two integers x and y. You are to find the number of good pairs of integers (a, b) such that l ≤ a, b ≤ r. Note that pairs (a, b) and (b, a) are considered different if a ≠ b.

Input

The only line contains four integers l, r, x, y (1 ≤ l ≤ r ≤ 109, 1 ≤ x ≤ y ≤ 109).

Output

In the only line print the only integer — the answer for the problem.

Examples

Input

1 2 1 2

Output

2

Input

1 12 1 12

Output

4

Input

50 100 3 30

Output

0

Note

In the first example there are two suitable good pairs of integers (a, b): (1, 2) and (2, 1).

In the second example there are four suitable good pairs of integers (a, b): (1, 12), (12, 1), (3, 4) and (4, 3).

In the third example there are good pairs of integers, for example, (3, 30), but none of them fits the condition l ≤ a, b ≤ r.

 

这道题感触挺深的。。。

不用数了，一共WA了20次

 

思路：

  题目要的是在(l, r)区间内，找一对(a, b)满足它们的gcd==x与lcm==y，那么我们该如何去寻这样的(a, b)？首先，令a==qx, b==px，则有gcd(qx, px)==x，即gcd(q, p)==1，故q、p互质，又知道lcm(qx, px)==y，于是有lcm(q, p)==(y/x)，又因为q、p互质，所以q*p==y/x。所以，我们只需要在（1～sqrt(y/x)）的区间内寻找这样一对满足条件的式子了。

 

细节：

1. 题目没有说y一定能被x整除，所以要特判这种状况。

2. 当两个数相等的时候，就是只有一种方法了。

3. 不要用l/x, r/x这样的方法简化，因为它们是向下取整的，可能会漏值，还是老实的用i*x>=l与i*x<=r这样的方式比较稳妥（WA on 39的原因）

 

完整代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
typedef long long ll;
ll l, r, x, y;     //寻这样的(a, b)，发现有a*b==x*y，我令a=qx,b=px,gcd(qx, px)=x,故gcd(q,  p)==1
ll gcd(ll a, ll b)       //我们只需要在(l/x, r/x)区间内寻找是否有一对y/x的公因子即可
{                           //gcd(p, q)==1满足该条件才行
    if(b==0) return a;      //则又有p、q互质，所以y/x==p*q此时满足条件的一对便是
    return gcd(b, a%b);
}
int main()
{
    while(scanf("%lld%lld%lld%lld", &l, &r, &x, &y)!=EOF)
    {
        if(y%x) { printf("0\n"); continue; }
        ll x_y=y/x;
        int ans=0;
        for(ll i=1; i*i<=x_y; i++)
        {
            if(i*x>=l && x_y%i==0 && x_y/i*x<=r && gcd(i, x_y/i)==1) ans+=(i==x_y/i?1:2);
        }
        printf("%d\n", ans);
    }
    return 0;
}