Dwarf X93677

The world is full of dwarves. Sometimes they like to kill some dragons, sheep or even witches, but people hate dwarves because they think they are the owners of this world.

The most important dwarf is called Remliw (Yeah, he is the big boss) and sometimes he likes to go for a ride to enjoy the landscape. Although he is so relaxed, he is also very important because if he gets killed then all the dwarves will leave the world just because they are Remliw-dependent.

Today is your last chance and you know that Remliw is going for a ride and he always starts at place 0, he takes his camel and then travels to place N. The places are numbered from left to right starting from 0 and ending at place N, where Remliw will rest for a while. Given that Remliw is so miserly, he always wants to reach place N as quickly as possible. Each place i has an associated tag t_i and the time that Remliw will spend to travel from place i to place j is t_j * 10^{|j−i| − 1}. Of course, Remliw is not dumb and he will never travel from place i to place j if i ≥ j , in other words he is always moving to a place with a bigger number.

To sum up, your task is to find the minimal time Remliw will spend to reach the place number N to be there at the right time and kill him.

Input

The input consist of a first line T, the number of test cases. Then, each test will start with the number N ( 1 ≤ N ≤ 10⁶) of places. After that, a line with N+1 numbers will follow, where the first number is the tag of the place 0, t₀, the second tag is the one for the place number 1, t₁, and so on... finally, the number N+1 is the tag of the place number N, t_N (1 ≤ t_i ≤ 200 ).

Output

The output should be a single integer per test case that is the time spent by Remliw to reach the place N.

In the first example, the optimal strategy is to always move one step to the very next place.

In the second example, the optimal strategy is to move directly to place N=3.

In the third example, the optimal strategy is to move to place 2, then to place N=3.