题目描述

给定五个整数 $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$，表示测试数据组数。

每组数据输入五个空格隔开的整数分别是 $k,\ l_1,\ r_1,\ l_2,\ r_2$。

输出格式

输出一共输出 $t$ 行，每行输出一个整数代表答案

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

提示

样例 1 解释

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

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

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

数据范围

对于 $100\%$ 的数据满足，$1\leq t\leq 10^4$，$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$。

• 其中 $30\%$ 的数据满足，$2\leq t,k\leq 100$，$1\leq l_1\leq r_1\leq 100$，$1\leq l_2\leq r_2\leq 100$。
• 另外 $10\%$ 的数据满足，$l_1=l_2=1,r_1=r_2\leq 10^9$。其余部分满足 $100\%$ 的范围。
• 其余所有数据符合 $100\%$ 的范围。