Somewhere in Andromeda, (yeah our neighbor galaxy!) Mystery Land, is having some signs of life. We just have found stairs there. But with different heights of each step.

Pictorially the stairs are like this:

The width of each step is same W, but for each stair numbered 'i', the total height of block of with W used for making the step is not uniform.

They used two functions for height Y[x] of each step number x.

            1. Y[x] = 2*x and

            2. Y[x] = Y[x-1] + 1

it's understood that, height of 0th step, floor, Y[0] = 0.

Sam, being not very good pilot (but an awesome mathematician), was getting bored in his lab, now he wonders if these stairs are to be covered with some royal carpet, what would be the required length of the stair-carpet! (The red part shown in the image!)

Now you will we given and array A of function number to be used for ith step. With A[i]=1 or 2. Depending on that value, height of ith step will be calculated.

Input:

First line containing T, the number of test cases.

Then T test cases are as follows:

    First line containing two Integers W, the width of steps and N, the number of steps.

    Next line containing N space separated integers A[1], A[2]...., A[N].

Output:

    For each case, print the total length of carpet needed to cover the stairs, on a newline.

Constraints:

1<= W <= 1000000000

1<=N<=100000

1<= T<= 100