F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 2301. -- [HAOI2011]Problem b

2301: [HAOI2011]Problem b

Time Limit: 50 Sec  Memory Limit: 256 MB
Submit: 7695  Solved: 3723
[Submit][Status][Discuss]

Description

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



Input

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

 

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

Source

[Submit][Status][Discuss]

HOME Back