O. Rabbit Jump
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Initially, a rabbit is at $$$(0,0)$$$ on a 2D plane, and it wants to go to $$$(x,y)$$$. It can perform one of the following three jumps:

  • Spend $$$A$$$ carrots to jump to $$$(x+1,y)$$$
  • Spend $$$B$$$ carrots to jump to $$$(x,y+1)$$$
  • Spend $$$C$$$ carrots to jump to $$$(2x,2y)$$$
Output the minimum number of carrots the rabbit needs.
Input

The first line contains an integer $$$T$$$ $$$(1\le T\le 10^4)$$$ - the number of test cases. For the next $$$T$$$ lines, each line contains $$$5$$$ integers $$$x,y,A,B,C$$$ $$$(0\le x,y\le 10^{9},0\le A,B,C\le 10^9)$$$.

Output

For each test case, output an integer, the minimum number of carrots the rabbit needs to jump to $$$(x,y)$$$.

Examples
Input
1
1 1 1 1 1
Output
2
Input
5
3 14 15 92 6
2718 2818 2 8 4
114 514 19 19 810
1024 1024 1 1 1
1249341 12313 1 1 1
Output
324
90
3950
12
34