CF955C.Sad powers

You're given Q queries of the form (L, R).

For each query you have to find the number of such x that L ≤ x ≤ R and there exist integer numbers a > 0, p > 1 such that x = a__p.

你将收到 Q 个形如 (L, R) 的查询。

对于每个查询，你需要找出满足 L ≤ x ≤ R 且存在整数 a > 0、p > 1 使得 x = a__p 的整数 x 的个数。

The first line contains the number of queries Q (1 ≤ Q ≤ 105).

The next Q lines contains two integers L, R each (1 ≤ L ≤ R ≤ 1018).

第一行包含查询次数 $Q$（$1 \le Q \le 10^5$）。

接下来的 $Q$ 行，每行包含两个整数 $L$ 和 $R$（$1 \le L \le R \le 10^{18}$）。

Output Q lines — the answers to the queries.

输出 Q 行——各查询的答案。

In query one the suitable numbers are 1 and 4.

在第一个查询中，合适的数字是 1 和 4。