{"raw_statement":[{"iden":"statement","content":"While Coach Fegla and Noura were flying back home from Marrakech after attending the ICPC2015 World Finals, they got really bored in their 6 - hour plane trip, so the coach decided to tell Noura some cool information about binary numbers and operators, and he gave her this challenge to pass the time.\n\nCoach Fegla asked her if she could find the number of ways to choose two integers, A and B, such that (L ≤ A, B ≤ R) and the XOR of the binary representations of A and B (without leading zeros) is palindrome in binary.\n\nFor example, , after removing leading zeros 101 is palindrome.\n\nThe first line of input contains an integer T (1 ≤ T ≤ 128), the number of test cases.\n\nEach test case will contain two space - separated integers L, R (0 ≤ L ≤ R ≤ 1012).\n\nFor each test case print the number of ways on a single line.\n\nA string of binary digits is a palindrome if it can be read the same from either direction.\n\nFor example: 0, 11 and 10101 are palindromes, while 10 and 10011 are not.\n\n means XOR, remember that:\n\n\n\n\n\n\n\n \n\n Warning: 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 ≤ 128), the number of test cases.Each test case will contain two space - separated integers L, R (0 ≤ L ≤ R ≤ 1012)."},{"iden":"output","content":"For each test case print the number of ways on a single line."},{"iden":"examples","content":"Input31 40 04 8Output12115"},{"iden":"note","content":"A string of binary digits is a palindrome if it can be read the same from either direction.For example: 0, 11 and 10101 are palindromes, while 10 and 10011 are not. means XOR, remember that:  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} $ with $ 0 \\leq L_k \\leq R_k \\leq 10^{12} $.  \nLet $ S_k = \\{ (A, B) \\in \\mathbb{Z}^2 \\mid L_k \\leq A, B \\leq R_k \\} $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 128 $  \n2. For each $ k $: $ 0 \\leq L_k \\leq R_k \\leq 10^{12} $  \n\n**Objective**  \nFor each test case $ k $, compute:  \n$$\nN_k = \\left| \\left\\{ (A, B) \\in S_k \\mid \\text{bin}(A \\oplus B) \\text{ is a binary palindrome (without leading zeros)} \\right\\} \\right|\n$$  \nwhere $ \\text{bin}(n) $ denotes the binary representation of $ n \\in \\mathbb{N}_0 $ without leading zeros, and a string is a palindrome if it equals its reverse.","simple_statement":"Count the number of pairs (A, B) where L ≤ A, B ≤ R, and the XOR of A and B (in binary, without leading zeros) is a palindrome.","has_page_source":false}