SP22534 PRJAN15B - Birthday Gift for SJ

今天是你最好的朋友 SJ 的生日，你想买一份礼物送给她。为了让SJ非常喜欢你的礼物，你希望礼物的价格是一个“有趣的数”。（听起来有点怪异，对吧？ :P） “有趣的数”的定义如下： 1. 形如 $x^y$ 的数，其中 $x \ge 2$ 且 $y \ge 2$。例如：4（$2^2$）、8（$2^3$）、9（$3^2$）等数都是有趣的数。 2. 如果两个或更多的有趣的数相加，所得的和也是一个有趣的数。例如：13 = 9 + 4，17 = 9 + 4 + 4 等都是有趣的数。

输入的第一行为一个整数 $t$，表示测试用例的数量。接下来的 $t$ 行中，每行包含两个整数 $a$ 和 $b$。

对于每个测试用例，输出一行，表示在 $a$ 和 $b$ 之间（包括 $a$ 和 $b$）的有趣数的数量。

- $1 \le t \le 10^5$ - $1 \le a, b \le 10^{18}$ ### 样例输入 ``` 3 1 4 7 10 15 20 ``` ### 样例输出 ``` 1 2 4 ``` 通过以上描述，你需要找到在给定范围内的有趣数并统计其数量。请仔细分析每种可能的有趣数并加以判断。 **本翻译由 AI 自动生成**