CF2044E Insane Problem

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,15)$ - $(5,45)$ - $(6,18)$ - $(6,54)$ - $(7,21)$ - $(7,63)$ 对于第四组测试样例，唯一有效的有序数对是 $(1,1\,000\,000\,000)$