Description

对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。

Input

第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k

Output

共n行，每行一个整数表示满足要求的数对(x,y)的个数

Sample Input

2

2 5 1 5 1

1 5 1 5 2

Sample Output

14

3

HINT

100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000

分析：

莫比乌斯反演，具体推导如下：

相当于一个矩阵前缀和

tip

还是这句话：板子打对

+-*/位运算，该加括号的一定要加括号

鸣谢

最近有点不愿写题了

刚才cyf来找我，看见我在写lct和数论，

ta表示我废了，这个时候应该写dp

很开心ta能在这个时候提醒我，确实，参加noip最需要练的还是dp

要不是他，我可能真的误入歧途了

这里写代码片#include
     
      #include
      
       #include
       
        #define ll long longusing namespace std;const int N=50005;bool no[N];int sshu[N],mu[N],tot=0,a,b,c,d,k,n;ll ans1,ans2;void cl(){    memset(no,0,sizeof(no));    mu[1]=1;    for (int i=2;i