{"raw_statement":[{"iden":"statement","content":"You're given _Q_ queries of the form (_L_, _R_).\n\nFor 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_."},{"iden":"input","content":"The first line contains the number of queries _Q_ (1 ≤ _Q_ ≤ 105).\n\nThe next _Q_ lines contains two integers _L_, _R_ each (1 ≤ _L_ ≤ _R_ ≤ 1018)."},{"iden":"output","content":"Output _Q_ lines — the answers to the queries."},{"iden":"example","content":"Input\n\n6\n1 4\n9 9\n5 7\n12 29\n137 591\n1 1000000\n\nOutput\n\n2\n1\n0\n3\n17\n1111"},{"iden":"note","content":"In query one the suitable numbers are 1 and 4."}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"给定 #cf_span[Q] 个形如 #cf_span[(L, R)] 的查询。\\n\\n对于每个查询，你需要找出满足 #cf_span[L ≤ x ≤ R] 且存在整数 #cf_span[a > 0] 和 #cf_span[p > 1] 使得 #cf_span[x = ap] 的 #cf_span[x] 的个数。\\n\\n第一行包含查询数量 #cf_span[Q] #cf_span[(1 ≤ Q ≤ 105)]。\\n\\n接下来的 #cf_span[Q] 行每行包含两个整数 #cf_span[L], #cf_span[R] #cf_span[(1 ≤ L ≤ R ≤ 1018)]。\\n\\n请输出 #cf_span[Q] 行 —— 每个查询的答案。\\n\\n在第一个查询中，符合条件的数是 #cf_span[1] 和 #cf_span[4]。 \\n\\n\"},{\"iden\":\"input\",\"content\":\"第一行包含查询数量 #cf_span[Q] #cf_span[(1 ≤ Q ≤ 105)]。接下来的 #cf_span[Q] 行每行包含两个整数 #cf_span[L], #cf_span[R] #cf_span[(1 ≤ L ≤ R ≤ 1018)]。\"},{\"iden\":\"output\",\"content\":\"请输出 #cf_span[Q] 行 —— 每个查询的答案。\"},{\"iden\":\"note\",\"content\":\"在第一个查询中，符合条件的数是 #cf_span[1] 和 #cf_span[4]。 \"}]\"","sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ Q \\in \\mathbb{Z} $ be the number of queries.  \nFor each query $ i \\in \\{1, \\dots, Q\\} $, let $ (L_i, R_i) \\in \\mathbb{Z}^2 $ denote the interval bounds.\n\nLet $ \\mathcal{P} = \\{ x \\in \\mathbb{Z}^+ \\mid \\exists\\, a \\in \\mathbb{Z}^+, p \\in \\mathbb{Z}, p \\geq 2 \\text{ such that } x = a^p \\} $ be the set of perfect powers (excluding $ p = 1 $).\n\n**Constraints**  \n1. $ 1 \\leq Q \\leq 10^5 $  \n2. For each query $ i $: $ 1 \\leq L_i \\leq R_i \\leq 10^{18} $\n\n**Objective**  \nFor each query $ i $, compute:  \n$$  \n\\left| \\mathcal{P} \\cap [L_i, R_i] \\right|  \n$$  \ni.e., the number of perfect powers in the interval $ [L_i, R_i] $.","simple_statement":null,"has_page_source":false}