Cabling

Time Limit: 2 Seconds    Memory Limit: 65536 KB

Mosjava misses his best friends at Isfahan and because the internet speed is slow and he love his friends, he wants to make a connection form Dezfoul to Isfahan by a high speed cable. In the way from Dezfoul to Isfahan there is a mountain the cable should cross above it. Help him to minimize the cable length. 

For each mountain the cable the post is on the top of it, which cable should make contact with it if needed. An example shown if figure below. 

Dezfoul is at location 0, every N mountaintop is at 1 to N and Isfahan is at N+1. The altitudes of Dezfoul and Isfahan are 0. 

Input

In the first line of input there is T, number of test-cases. 

Each test case started with (1≤n≤1000), Number of mountain. 

Then a line containing N space-separated integers, a1,a2,…,an representing the altitudes of mountain. 0≤a1≤a2≤⋯≤an≤1000000 

Output

For each test-case, print minimum length of cable with 7 digit after decimal point. 

Sample Input

2
4
3 4 1 4
5
0 0 4 0 0

Sample Output

10.6995968
10.0000000

Submit