C. Sad powerstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou'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.InputThe 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).OutputOutput Q lines — the answers to the queries.ExampleInput61 49 95 712 29137 5911 1000000Output2103171111NoteIn query one the suitable numbers are 1 and 4. 
Input61 49 95 712 29137 5911 1000000
Output2103171111
['binary search', 'math', 'number theory', '*2100']