E. Insane Problem
时间限制：每测试 $2$ 秒
内存限制：每测试 $256$ MB

Wave 得到了五个整数 $k$, $l_1$, $r_1$, $l_2$, $r_2$。她希望你能帮忙计算满足以下所有条件的有序对 $(x, y)$ 的数量：

• $l_1 \le x \le r_1$
• $l_2 \le y \le r_2$
• 存在非负整数 $n$ 使得 $\frac{y}{x} = k^n$

输入格式
第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试数据组数。
每组测试数据包含一行五个整数 $k$, $l_1$, $r_1$, $l_2$, $r_2$ ($2 \le k \le 10^9$, $1 \le l_1 \le r_1 \le 10^9$, $1 \le l_2 \le r_2 \le 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, 1000000000)$。