Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Binary Rhodium

By shefin · Limits 2.5s, 512 MB

Xenon is a great alchemist. Recently, he has decided to perform a special type of transmutation. But to make that happen, he needs a lot of rhodium, the most precious metal in the world. After a huge exploration, he has found a vault of rhodium on a far island. The vault has a strange mechanism. There is a keypad outside the vault. Anyone can insert a decimal number into the vault using that keypad. If a number XX is inserted, the following happens:

  1. The number XX is converted into a binary number. The converted binary number does not have any leading zeros.

  2. In the converted binary number, for any ithi^{th} digit from the left, if there exists (i+1)th(i+1)^{th} digit:

    • Xenon gets aa amount of rhodium if the ithi^{th} digit is 00 and the (i+1)th(i+1)^{th} digit is 00.

    • Xenon gets bb amount of rhodium if the ithi^{th} digit is 00 and the (i+1)th(i+1)^{th} digit is 11.

    • Xenon gets cc amount of rhodium if the ithi^{th} digit is 11 and the (i+1)th(i+1)^{th} digit is 00.

    • Xenon gets dd amount of rhodium if the ithi^{th} digit is 11 and the (i+1)th(i+1)^{th} digit is 11.

For example, if Xenon inserts 1414 into the vault, the binary form will be 11101110. So, Xenon will receive dd amounts of rhodium for “1111“ twice as “1111“ occurs two times in the binary. He will also receive cc amount of rhodium for “1010” in the binary. So, the total amount of rhodium Xenon will receive is = d+d+cd+d + c.

Now, Xenon wants to know what is the total amount of rhodium he can get if he inserts all the numbers between LL and RR inclusive.

Input

The first line contains an integer T(1T5×105)T(1\leq T\leq 5\times10^5), the number of the test cases.

In each test case, the first line contains two space-separated integers L(1L1015)L(1\leq L\leq 10^{15}) and R(LR1015)R(L\leq R\leq 10^{15}). The next line contains four space-separated integers a,b,c,d(0a,b,c,d100)a, b, c, d (0\leq a, b, c, d \leq 100) described in the statement.

Output

In each test case, print an integer in a line containing the total amount of rhodium Xenon can get if he inserts all the numbers between LL and RR inclusive.

Sample

InputOutput
2
1 2
5 1 3 2
2 5
4 12 3 3
3
28

Discussion

Statistics


71% Solution Ratio

YouKnowWhoEarliest, 3w ago

Wojciech.324122Fastest, 0.5s

Wojciech.324122Lightest, 10 MB

tanzim_bnShortest, 873B

Submit

Login to submit

Editorial

At first, let’s simplify the problem a little bit. If we know the answer ARA_RAR​ for [1,R][1, R][1,...

Toph uses cookies. By continuing you agree to our Cookie Policy.