题目描述

Wave 有五个整数 $k$ 、 $l_1$ 、 $r_1$ 、 $l_2$ 和 $r_2$ ，她想要你帮她数出有多少对有序数对 $(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)$，代表测试样例数量。

接下来的 $t-1$ 行，每行代表一组测试样例，包括五个整数 $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)$ 的组数。

样例

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

12
1999999987
6
1
197

样例说明

对于第三组测试样例，以下有序数对是符合条件的：

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

对于第四组测试样例，唯一有效的有序数对是 $(1,1\,000\,000\,000)$

来源

Codeforces 2044E，英文题名 Insane Problem。