#P3455. [POI2007] ZAP-Queries

    ID: 4931 远端评测题 2000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2007POI最大公约数,gcd莫比乌斯反演

[POI2007] ZAP-Queries

题目描述

密码学家正在尝试破解一种叫 BSA 的密码。

他发现,在破解一条消息的同时,他还需要回答这样一种问题:

给出 a,b,da,b,d,求满足 1xa1 \leq x \leq a1yb1 \leq y \leq b,且 gcd(x,y)=d\gcd(x,y)=d 的二元组 (x,y)(x,y) 的数量。

因为要解决的问题实在太多了,他便过来寻求你的帮助。

输入格式

输入第一行一个整数 nn,代表要回答的问题个数。

接下来 nn 行,每行三个整数 a,b,da,b,d

输出格式

对于每组询问,输出一个整数代表答案。

2
4 5 2
6 4 3
3
2

提示

数据规模与约定

对于全部的测试点,保证 1n5×1041 \leq n \leq 5 \times 10^41da,b5×1041 \leq d \leq a,b \leq 5 \times 10^4