Background

:::epigraph ___, ___ frowned: What does it mean to fish at the bottom of the river? :::

Problem Description

TSUCE's final exam is over. The grader, Big K, looked at Little T's terrible paper.

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

• 【Pull Up by the Roots】. This move can be used at most $a_1$ times. It updates Little T's current score $x$ by taking the square root, multiplying by $10$, and rounding down, i.e., $x \leftarrow \lfloor 10\sqrt{x} \rfloor$.
• 【Thirty-Seventy Split】. This move can be used at most $a_2$ times. It updates Little T's current score $x$ by multiplying by $0.7$, adding $30$, and rounding down, i.e., $x \leftarrow \lfloor 0.7x + 30 \rfloor$.
• 【Plant Five, Get Six】. This move can be used at most $a_3$ times. It updates Little T's current score $x$ by multiplying by $1.2$ and rounding down, i.e., $x \leftarrow \lfloor 1.2x \rfloor$.
• 【Five Blessings at the Door】. This move can be used at most $a_4$ times. It updates Little T's current score $x$ by adding $5$, i.e., $x \leftarrow x + 5$.

The four moves can be used in any order. Please help Big K find a reasonable way to use these moves so that Little T gets the highest possible score.

Input Format

The first line contains an integer $T\ (1 \le T \le 3 \times 10^5)$, which indicates the number of testdata.

Each testdata consists of one line with $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)$, which represent Little T's initial score and the maximum number of times each of the four moves can be used.

Output Format

For each testdata, output one line with one integer, representing the highest score Little T can achieve.

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

70
118
148
71
98703086085238798121046930830507710
168
232

Hint

Sample 1 Explanation

For the $1$-st testdata, Little T starts with a great score of $1$ point. Big K can use each move at most once. Big K can use the following strategy:

• First use 【Thirty-Seventy Split】, and Little T becomes $\lfloor 0.7x + 30 \rfloor = \lfloor 0.7 \times 1 + 30 \rfloor = 30$ points.
• Then use 【Pull Up by the Roots】, and Little T becomes $\lfloor 10\sqrt{x} \rfloor = \lfloor 10\sqrt{30} \rfloor = 54$ points.
• Then use 【Five Blessings at the Door】, and Little T becomes $54 + 5 = 59$ points.
• Then use 【Plant Five, Get Six】, and Little T becomes $\lfloor 1.2x \rfloor = \lfloor 1.2 \times 59 \rfloor = 70$ points.

Translated by ChatGPT 5