L. Haitei Raoyue
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

TSUCE's final exams are over! The grading teacher, Big K, looked at Little T's horrible exam paper.

Therefore, he decided to use the following tricks to save Little T, who scored $$$x$$$ points:

  • Operation A, this trick can be used at most $$$a_1$$$ times. It takes the square root of Little T's current score $$$x$$$, multiplies it by 10, and rounds down, i.e., $$$x \leftarrow \lfloor 10 \sqrt{x} \rfloor$$$.
  • Operation B, this trick can be used at most $$$a_2$$$ times. It multiplies Little T's current score $$$x$$$ by $$$0.7$$$, adds 30, and rounds down, i.e., $$$x \leftarrow \lfloor 0.7x + 30 \rfloor$$$.
  • Operation C, this trick can be used at most $$$a_3$$$ times. It multiplies Little T's current score $$$x$$$ by $$$1.2$$$ and rounds down, i.e., $$$x \leftarrow \lfloor 1.2x \rfloor$$$.
  • Operation D, this trick can be used at most $$$a_4$$$ times. It adds $$$5$$$ to Little T's current score $$$x$$$, i.e., $$$x \leftarrow x + 5$$$.

Please help Big K find a valid way to use these tricks so that Little T can obtain the maximum possible score.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 3 \times 10^5$$$), representing the number of test cases.

Each test case consists of a single line containing 5 integers $$$x$$$, $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, $$$a_4$$$ ($$$1 \le x \le 100, 0 \le a_1, a_2, a_3, a_4 \le 400$$$), representing Little T's initial score and the maximum number of times Big K can use each trick.

Output

For each test case, output a single line with an integer representing the maximum score Little T can obtain.

Example
Input
7
1 1 1 1 1
50 2 1 1 2
99 0 1 2 1
10 2 0 0 3
100 400 400 400 400
75 1 7 3 0
1 3 7 4 3
Output
70
118
148
71
98703086085238798121046930830507710
168
232
Note

For the 1st test case, Little T initially scored $$$1$$$ point, and Big K can use each trick at most once. Big K can adopt the following strategy:

  • First, use Operation B. Little T's score becomes $$$\lfloor 0.7x+30 \rfloor = \lfloor 0.7 \times 1 +30 \rfloor = 30$$$ points.
  • Next, use Operation A,. Little T's score becomes $$$\lfloor 10\sqrt{x} \rfloor = \lfloor 10\sqrt{30} \rfloor = 54$$$ points.
  • Next, use Operation D. Little T's score becomes $$$54 + 5 = 59$$$ points.
  • Next, use Operation C. Little T's score becomes $$$\lfloor 1.2x \rfloor = \lfloor 1.2 \times 59 \rfloor = 70$$$ points.