At time 0, F frogs are sitting on a straight line. All the positions of the frogs are non-negative integer numbers. Every second, all the frogs jump. Each of the frogs has its own velocity, i.e., every second the i-th frog jumps Vi units. Every frog jumps to its right. The line is divided into N + 1 contiguous segment. The left end of the first segment is always 0 and the right end of the (N + 1)-th segment is 109. The segments are denoted by a sequence of N positive integers, the right end point of first N segments. Every segment except the first one starts from the first point after the right endpoint of the last segment. For example, if N = 1 and the sequence has 1 integer number 10, then there are two segments, one is from 0 to 10 and another is from 11 to 109, both inclusive. You are given the initial positions of all the F frogs and a sequence of positive integers describing the segments. Find the minimum time it will take all the frogs to reach a single segment. A frog is said to be on a segment if and only if it’s sitting on some points inside the segment (including the endpoints). Please note that a frog is not said to be inside a segment when it’s jumping. Input Input starts with a single positive integer, 1 ≤ T ≤ 10, on a single line, denoting the number of test cases. Each of the following T test cases has the following 5 lines,
2/2 Sample Output Case 1: 0 Case 2: 1