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 is inserted, the following happens:
The number is converted into a binary number. The converted binary number does not have any leading zeros.
In the converted binary number, for any digit from the left, if there exists digit:
Xenon gets amount of rhodium if the digit is and the digit is .
Xenon gets amount of rhodium if the digit is and the digit is .
Xenon gets amount of rhodium if the digit is and the digit is .
Xenon gets amount of rhodium if the digit is and the digit is .
For example, if Xenon inserts into the vault, the binary form will be . So, Xenon will receive amounts of rhodium for ““ twice as ““ occurs two times in the binary. He will also receive amount of rhodium for “” in the binary. So, the total amount of rhodium Xenon will receive is = .
Now, Xenon wants to know what is the total amount of rhodium he can get if he inserts all the numbers between and inclusive.
The first line contains an integer , the number of the test cases.
In each test case, the first line contains two space-separated integers and . The next line contains four space-separated integers described in the statement.
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 and inclusive.
Input | Output |
---|---|
2 1 2 5 1 3 2 2 5 4 12 3 3 | 3 28 |