Binary Rhodium

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 $X$ is inserted, the following happens:

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

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

   • Xenon gets $a$ amount of rhodium if the $i^{th}$ digit is $0$ and the $(i+1)^{th}$ digit is $0$.

   • Xenon gets $b$ amount of rhodium if the $i^{th}$ digit is $0$ and the $(i+1)^{th}$ digit is $1$.

   • Xenon gets $c$ amount of rhodium if the $i^{th}$ digit is $1$ and the $(i+1)^{th}$ digit is $0$.

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

For example, if Xenon inserts $14$ into the vault, the binary form will be $1110$. So, Xenon will receive $d$ amounts of rhodium for “$11$“ twice as “$11$“ occurs two times in the binary. He will also receive $c$ amount of rhodium for “$10$” in the binary. So, the total amount of rhodium Xenon will receive is = $d+d + c$.

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

Input

The first line contains an integer $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(1\leq L\leq 10^{15})$ and $R(L\leq R\leq 10^{15})$. The next line contains four space-separated integers $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 $L$ and $R$ inclusive.

Sample

Input	Output
2 1 2 5 1 3 2 2 5 4 12 3 3	3 28