You've been put in charge of creating the problems for a certain high-profile programming contest series.
The series will consist of one or more contests of exactly 4 problems each. Every problem has a difficulty rating (an integer between 1 and 100, inclusive), and the ratings of the 4 problems in each contest must be strictly increasing, but with a difference of no more than 10 between consecutive problems. In other words, if the problems in a contest have difficulties a, b, c, and d (in order), then the inequalities a < b < c < d, b - a ≤ 10, c - b ≤ 10, d - c ≤ 10 must all hold.
You've been given an ordered list of N problems to use. Being an experienced problemsetter, you may also write some new problems to insert at any positions in the list, each with an integer difficulty between 1 and 100, inclusive. The final list of problems must still include the original N problems in their original order, though (with your new problems optionally mixed in).
Once the problem list is finalized, the first 4 problems (in order) will form a contest, the next 4 problems will form another contest, and so on. Note that the number of problems in the list must be divisible by 4, and that each of the contests formed must feature a valid ordered set of 4 problems. What's the minimum number of additional problems you must write in order to create a set of valid contests?
Input
Input begins with an integer T, the number of contest series you need to create. For each series, there is first a line containing the integer N, then a line containing N space-separated integers, the ith of which is Di, the difficulty rating of the ith existing problem.
Output
For the ith series, print a line containing "Case #i: " followed by the minimum number of additional problems you'll need to write.
Constraints
1 ≤ T ≤ 50
1 ≤ N ≤ 100,000
1 ≤ Di ≤ 100
Explanation of Sample
In the first series, the four problems given are already a valid contest, so no new problems need to be written. In the second series, the four existing problems most certainly do not form a valid contest, due to the gap between the third and fourth ones - one possible way to salvage the situation is to add three new problems with difficulties 30, 29, and 30 after the third problem, as well as a problem with difficulty 42 at the end, creating two valid contests: [15, 20, 25, 30] and [29, 30, 40, 42].
Input sample:
Code: Select all
5
4
10 15 25 30
4
15 20 25 40
3
3 3 3
8
60 90 61 62 63 91 92 93
11
5 14 30 32 39 46 47 47 30 58 47Code: Select all
Case #1: 0
Case #2: 4
Case #3: 9
Case #4: 4
Case #5: 9