eolymp
bolt
Try our new interface for solving problems
Problems

Hyper-drive

Hyper-drive

Time limit 1 second
Memory limit 128 MiB
prb1184

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 (p[1], p[2], ..., p[n]) and the coordinates of Q be (q[1], q[2], ..., q[n]). 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 x 4 x 3) three dimensional universal space can be divided into 60 three dimensional unit hyper-cubes (1 x 1 x 1).

prb1184-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 data

The first line contains an integer n (n501) 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 < D10) 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 nonnegative and fit within 32-bit signed integer.

Output data

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.

Examples

Input example #1
2
2
10 10
10 13
1
10
20
Output example #1
Case 1: 0
Case 2: 10