[HAOI2011]Problem b

[HAOI2011]Problem b

Description

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

\[\sum_{a\le x\le b} \sum_{c\le y\le d} [\gcd(x,y)=k]\]

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

Output

14
3

HINT

  • 100%的数据满足:\(1\le n\le 50000,1\le a\le b\le 50000,1\le c\le d\le 50000,1\le k\le 50000\)

Source

bzoj2301

信息

难度
9
分类
(无)
标签
递交数
3
已通过
2
通过率
67%
上传者