{"raw_statement":[{"iden":"statement","content":"After Noura's brother, Tamim, finished his junior training, coach Fegla was impressed with his progress. He told Noura that if Tamim would solve the following problem in SCPC2015 and yet does not qualify to the ACPC2015, he will give him a chance to participate unofficially in it.\n\nThe problem goes as follows:\n\nGiven L and R, how many integers between them have a prime number of ones in their binary representation?\n\nCan you help Tamim participate in the ACPC2015?\n\nThe first line of input contains an integer T (1 ≤ T ≤ 105), the number of test cases.\n\nEach test case will consist of two space - separated integers: L and R (0 ≤ L ≤ R ≤ 105).\n\nFor each test case, print the number of integers between L and R that have a prime number of ones in their binary representation.\n\nWarning: large Input/Output data, be careful with certain languages.\n\n"},{"iden":"input","content":"The first line of input contains an integer T (1 ≤ T ≤ 105), the number of test cases.Each test case will consist of two space - separated integers: L and R (0 ≤ L ≤ R ≤ 105)."},{"iden":"output","content":"For each test case, print the number of integers between L and R that have a prime number of ones in their binary representation."},{"iden":"examples","content":"Input32 101 193 101Output61365"},{"iden":"note","content":"Warning: large Input/Output data, be careful with certain languages."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $, let $ L_k, R_k \\in \\mathbb{Z} $ satisfy $ 0 \\leq L_k \\leq R_k \\leq 10^5 $.  \nLet $ \\text{popcount}(n) $ denote the number of 1-bits in the binary representation of $ n \\in \\mathbb{Z}_{\\geq 0} $.  \nLet $ \\mathbb{P} $ denote the set of prime numbers.\n\n**Constraints**  \n1. $ 1 \\leq T \\leq 10^5 $  \n2. For each $ k \\in \\{1, \\dots, T\\} $: $ 0 \\leq L_k \\leq R_k \\leq 10^5 $\n\n**Objective**  \nFor each test case $ k $, compute:  \n$$  \n\\left| \\left\\{ n \\in \\mathbb{Z} \\mid L_k \\leq n \\leq R_k \\text{ and } \\text{popcount}(n) \\in \\mathbb{P} \\right\\} \\right|  \n$$","simple_statement":"Count how many integers in [L, R] have a prime number of 1s in their binary representation.","has_page_source":false}