يوجد $n$ من الرنانات موضوعة بالترتيب على طول ممر. إزاحة التردد الحالية للرنان رقم $i$ هي $a_i$، وإزاحته المستهدفة هي $b_i$.

لا يمكن تفعيل جهاز الضبط إلا من أحد طرفي الممر. في العملية الواحدة، يمكنك اختيار أي عدد صحيح غير صفري $x$ وتنفيذ إحدى العمليتين التاليتين:

1. اختر $k$ ($1 \le k \le n$) وأضف $x$ إلى كل عدد في البادئة $a_1, a_2, \ldots, a_k$؛
2. اختر $k$ ($1 \le k \le n$) وأضف $x$ إلى كل عدد في اللاحقة $a_k, a_{k+1}, \ldots, a_n$.

قد يكون $x$ موجباً أو سالباً. وبغض النظر عن مقدار $|x|$، يُحتسب هذا التعديل كعملية واحدة بالضبط.

أوجد الحد الأدنى لعدد العمليات اللازمة لتحويل المتتالية $a$ إلى المتتالية $b$.

الإدخال

يحتوي السطر الأول على عدد صحيح $T$ ($1 \le T \le 10^4$)، وهو عدد حالات الاختبار.

لكل حالة اختبار:

• يحتوي السطر الأول على عدد صحيح $n$ ($1 \le n \le 2 \times 10^5$).
• يحتوي السطر الثاني على $n$ من الأعداد الصحيحة $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$).
• يحتوي السطر الثالث على $n$ من الأعداد الصحيحة $b_1, b_2, \ldots, b_n$ ($-10^9 \le b_i \le 10^9$).

من المضمون أن مجموع $n$ عبر جميع حالات الاختبار لا يتجاوز $2 \times 10^5$، وأن مجموعي $\sum |a_i - a_{i-1}|$ ($i \ge 2$) و $\sum |b_i - b_{i-1}|$ ($i \ge 2$) عبر جميع حالات الاختبار لا يتجاوزان $10^4$ على التوالي.

الإخراج

لكل حالة اختبار، اطبع عدداً صحيحاً واحداً في سطر منفصل يمثل الحد الأدنى لعدد العمليات.

أمثلة

الإدخال 1

4
3
0 0 0
-1 2 0
3
0 0 0
3 1 4
4
1 4 2 8
6 9 7 13
2
-7 10
-7 10

الإخراج 1

2
3
1
0

ملاحظة

بالنسبة لحالة الاختبار الأولى، فإن إحدى المتتاليات الممكنة من العمليات هي:

1. إضافة $-3$ إلى بادئة طولها $1$، للحصول على $[-3, 0, 0]$.
2. إضافة $2$ إلى بادئة طولها $2$، للحصول على $[-1, 2, 0]$.

بالنسبة لحالة الاختبار الثالثة، تكفي إضافة $5$ إلى المتتالية بأكملها.