[HAOI2011]Problem b

时间限制:50s      空间限制:256MB

题目描述

对于给出的n个询问,每次求有多少个数对(x,y),满足axbcyd,且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

 


提示


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


题目来源

没有写明来源