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 nth position. Rules of the game are simple, you can move from ith place to jth if j>i and j-i is a fibonacci number.
For moving from ith position to jth 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)
1 <= t <= 10 1 <= n <= 20000 0 <= cost[i] <= 10^9
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]
Print one line for each test case: Minimum money that Nick has to pay.