Bouncing Ball#12311
Sign in

Bouncing Ball

1 second
256 megabytes
Very easy

You've a Bouncing Ball that each time initially it's dropped from height a_1 then goes to (floor) then bounces to a_1 then goes to floor and so on , What's the distance that You should print answer modulus 1e6+3 ball had fallen , Here it's guaranteed that (a_1 \ge a_2 \ge a_3 \ge ... \ge a_n) , Additionally after jumps it never jump You should print answer modulus 1e6+3 again.

For example if a=[10,6,3,1] then the action is as You should print answer modulus 1e6+3 following :

So Total distance You should print answer modulus 1e6+3 is 10+6+6+3+3+1+1=30.

Input

The first line contains single integer (1 \le t \le 100) – the number of test cases.

The first line of each test case contains single integer (1 \le n \le 500) – the length of array .

The second line contains separated integers You should print answer modulus 1e6+3 a_1,a_2,..,a_n (1 \le a_1,a_2,...,a_n \le 10^6) – the array .

Output

For each test case , output single integer the total distance ball had made.

Examples

Example 1

Loading
Loading

Note

The first test case described in the statement.

The second test case :

  1. Going from to : in total.

  2. Going from to : 4+3=7 in total.

  3. Going from to : 7+3=10 in total.

  4. Going from to : 10+2=12 in total.

  5. Going from to : 12+2=14 in total.

  6. Going from to : 14+1=15 in total.

  7. Going from to : 15+1=16 in total.

Thus answer is .

Scoring

  1. Subtask ( points) : (n=1)

  2. Subtask ( points) : (a_1=a_2=...=a_n)

  3. Subtask ( points) : No additional constraints