[HAOI2011]问题B

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 b.in 输出文件 b.out


题目描述:

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


输入格式:

第一行一个整数n,接下来n行每行五个整数,分别表示abcdk


输出格式:

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


样例输入:

2

2 5 1 5 1

1 5 1 5 2


样例输出:

14

3


数据范围:

10%的数据满足:1≤n≤51≤a≤b≤1001≤c≤d≤100

30%的数据满足:1≤n≤10

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