← 返回题目列表

Codeforces · 2044/E

E. 疯狂的问题

中文机器翻译题面 查看原题

Wave 被赋予五个整数 $$$k$$$、$$$l_1$$$、$$$r_1$$$、$$$l_2$$$ 和 $$$r_2$$$。 Wave 希望你帮助她计算有序对 $$$(x, y)$$$ 的数量,以满足以下所有条件:

- $$$l_1 \leq x \leq r_1$$$。
- $$$l_2 \leq y \leq r_2$$$。
- 存在一个非负整数 $$$n$$$ 使得 $$$\frac{y}{x} = k^n$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的唯一行包含五个整数 $$$k$$$、$$$l_1$$$、$$$r_1$$$、$$$l_2$$$ 和 $$$r_2$$$ ($$$2 \leq k \leq 10^9, 1 \leq l_1 \leq r_1 \leq 10^9, 1 \leq l_2 \leq r_2 \leq 10^9$$$)。

输出

对于每个测试用例,在新行上输出匹配的有序对 $$$(x, y)$$$ 的数量。

示例

输入 #1

5
2 2 6 2 12
2 1 1000000000 1 1000000000
3 5 7 15 63
1000000000 1 5 6 1000000000
15 17 78 2596 20914861

输出 #1

12
1999999987
6
1
197

注意

在第三个测试用例中,匹配的有序对如下:

- $$$(5,15)$$$
- $$$(5,45)$$$
- $$$(6,18)$$$
- $$$(6,54)$$$
- $$$(7,21)$$$
- $$$(7,63)$$$

在第四个测试用例中,唯一有效的有序对是 $$$(1,1\,000\,000\,000)$$$