Hyper-drive#1184
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, there exist many explanations and theories about wormholes and hyper-drives. Many say that hyper-drive allows travel through higher dimensions. In this problem, you are to calculate the cost of traveling through higher dimensions based on a theory described by our old mad friend Arif. I am sure you know who Arif is. If you do not, you can ask your teammates.
Let P and Q be two points in an -dimensional space, with coordinates respectively P (p_1, p_2, , p_n) and Q (q_1, q_2, , q_n). The universal -dimensional space is divided into unit -dimensional hypercubes. For a visual example, see below how a (5 \times 4 \times 3) three-dimensional universal space can be divided into three-dimensional unit hypercubes (1 \times 1 \times 1).
Please do not ask for visual examples in higher dimensions. The cost of traveling from one -dimensional point P to another -dimensional point Q is equal to "the number of different -dimensional unit hypercubes the straight segment joining these two points passes through." Your task is to calculate this cost. For example, in the above figure, the cost of traveling from C to E is units, as segment EC passes through different unit three-dimensional hypercubes.
The first line contains the number of test cases (n \leq 501). Each test case starts with an integer (0 < D \leq 10) — the dimension in which the cost is measured. Each of the next two lines contains integers. The integers of the first line describe the coordinates of P; the integers of the second line describe the coordinates of Q. All numbers are non-negative, -bit signed integers.
For each test case, output the cost of traveling from P to Q as an integer, one per line.
Example 1