Гипер-устройство
Гипер-устройство - это часто используемый термин в научно-фантастических рассказах. Хотя многие считают, что гипер-устройство не возможно, тем не менее существует большое количество теорий, описывающих черные дыры и гипер-устройства. Говорят, что гипер-устройство позволяет путешествовать в более высоких измерениях. В этой задаче Вас следует вычислить стоимость путешествия по большим измерениям согласно теории старого сумасшедшего друга Арифа. Я уверен, что вы знаете кто такой Ариф. Если нет, то можете спросить у своих товарищей по команде.
Пусть P и Q - две точки в n-мерном пространстве, координаты которых соответственно равны P (p[1], p[2], ..., p[n]), и Q (q[1], q[2], ..., q[n]). Универсальное n-мерное пространство разбито на маленькие единичные n-мерные гиперкубы. Для наглядного примера представленное ниже (5 x 4 x 3) трехмерное пространство разбито на 60 трехмерных единичных кубов (1 x 1 x 1).
Давайте обойдемся без визуализации примеров в больших размерностях. Стоимость путешествия от одной n-мерной точки P до другой n-мерной точки Q равна "количеству разных n-мерных единичных гиперкубов, которое пересекает отрезок, соединяющий эти две точки". Вам следует вычислить эту стоимость. Например, на рисунке сверху стоимость путешествия от C до E равно 10 единицам, так как отрезок EC проходит через 10 разных единичных трехмерных гиперкубов.
Входные данные
Первая строка содержит количество тестов n (n ≤ 501). Каждый тест начинается целым числом D (0 < D ≤ 10) - размерностью, в которой будет измеряться стоимость. Каждая из следующих двух строк содержит D целых чисел. D чисел первой строки задают координаты P, а D чисел второй строки задают координаты Q. Все числа не отрицательны и являются 32-битовыми знаковыми целыми.
Выходные данные
Для каждого теста вывести в одной строке стоимость путешествия из P в Q, которая является целым числом.