F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 2301. -- [HAOI2011]Problem b

2301: [HAOI2011]Problem b

Time Limit: 50 Sec  Memory Limit: 256 MB
Submit: 7788  Solved: 3793
[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