# Hyper-drive

Hyper-drive is a term that is very frequently used in science fiction stories. Although, many believe that hyper-drive is not at all possible, many explanations and theories exist on the existence of wormholes and hyper-drives. Many say that hyper-drive is a journey through higher dimensions. In this problem we will try to calculate our cost of traveling through higher dimension based on a theory described by our old mad friend Arif. I am sure that you remember Arif. You can ask your team mates if you don’t remember. Let P and Q be two points in n-dimensional space. Let the coordinates of P be (p1, p2, . . . , pn) and the coordinates of Q be (q1,q2,...,qn). The universal n-dimensional space is divided into many unit n-dimensional hyper-cubes. For visual example look at the picture below to realize how a (5 × 4 × 3) three dimensional universal space can be divided into 60 three dimensional unit hyper-cubes (1×1×1). Please don’t ask for a visual example in higher dimension. The cost of traveling from one n- dimensional P point to another n-dimensional point Q is equal to “the number of different n-dimensional unit hyper-cubes that the straight line joining these two points passes through.”. Your job is to determine this cost for two given points. For example in the previous picture the cost of hyper-drive from C to E is 10 units as EC passes through 10 different three dimensional hyper-cubes. Input The first line of the input file contains an integer N (N ≤ 501) that denotes how many sets of inputs are there. The description of each set is given below: Each set starts with an integer D (0 < D ≤ 10) which denotes in what dimension we want to measure the cost. Each of the next two lines contains D integers. The D integers in the first line denote the coordinates for P and the D integers in the second line denotes the coordinates for Q. All these integers will be positive and fit within 32-bit signed integer.

2/2 Output For each set of input produce one line of output. This line contains the serial of the output and then the cost of traveling from P to Q, which will obviously be an integer. Look at the sample output below for details. Note: In the first sample output for sample input the cost of traveling from (10, 10) to (10, 13) is shown zero because the line connecting these two points does not really enter any two dimensional hyper-cube. The line just goes along the edges of the two dimensional hyper-cubes. Sample Input 2 2 10 10 10 13 1 10 20 Sample Output Case 1: 0 Case 2: 10