Description: 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 = ap. Input Format: 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). Output Format: Output Q lines — the answers to the queries. Note: In query one the suitable numbers are 1 and 4.