## Minimum Cost

Time Limit: 2 sec
Memory Limit: 256 MB
Attempts: 21
Accuracy: 0.00%
Author: Nitish

Nick and his friend Mick are playing a game .The game is that there are n positions and starting from first position you have to reach the final n^{th} position. Rules of the game are simple, you can move from i^{th} place to j^{th} if j>i and j-i is a fibonacci number.

For moving from i^{th} position to j^{th} position a person has to pay |cost[i]-cost[j]| rupees. Nick is our school friend and is facing financial problems. Help him to pay the minimum amount to Mick.

Here cost is number written at each of n positions and fibonacci series is 1, 1, 2, 3, 5, 8... and so on. for more you can google it.

Note: |x| = x if x > 0 else |x| = (-x)

### Constraints:

1 <= t <= 10

1 <= n <= 20000

0 <= cost[i] <= 10^9

### Input Format:

First line contains number of test cases t

Second line contain number of positions n

Third line contain n integers, cost at each position cost[i]

### Output Format:

Print one line for each test case: Minimum money that Nick has to pay.

### Sample Input:

3

3

1 2 3

4

1 2 3 3

5

5 2 4 2 7

### Sample Output:

2

2

4

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED

2 years ago

cpp14

0.00 sec

0 KB

4 years ago

cpp14

0.00 sec

0 KB

4 years ago

cpp

0.00 sec

0 KB

4 years ago

cpp

0.00 sec

0 KB

4 years ago

cpp

0.00 sec

0 KB