import kotlin.math.abs

fun sum(a1: Int, a2: Int, b1: Int, b2: Int) = abs(a1 - a2) + abs(b1 - b2)

fun main() {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val a = readLine()!!.split(' ').map { it.toInt() }.toIntArray()
        val b = readLine()!!.split(' ').map { it.toInt() }.toIntArray()

        var sum = 0L
        for (i in 1 until n) {
            if (sum(a[i - 1], a[i], b[i - 1], b[i]) > sum(a[i - 1], b[i], b[i - 1], a[i]))
                a[i] = b[i].also { b[i] = a[i] }
            sum += sum(a[i - 1], a[i], b[i - 1], b[i])
        }
        println(sum)
    }
}

fun main() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(' ').map { it.toInt() }.toIntArray()

    for (v in a) {
        var ans = 20
        for (cntAdd in 0..15) {
            for (cntMul in 0..15) {
                if (((v + cntAdd) shl cntMul) % 32768 == 0)
                    ans = minOf(ans, cntAdd + cntMul)
            }
        }
        print("$ans ")
    }
}

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++) 

int main(){
    int tc;
    scanf("%d", &tc);
    while (tc--) {
        int n;
        scanf("%d", &n);
        vector<int> a(n);
        forn(i, n) scanf("%d", &a[i]);
        long long ans = 1e18;
        int mx = *max_element(a.begin(), a.end());
        for (int x : {mx, mx + 1}){
            long long cnt1 = 0, cnt2 = 0;
            forn(i, n){
                cnt2 += (x - a[i]) / 2;
                cnt1 += (x - a[i]) % 2;
            }
            long long dif = max(0ll, cnt2 - cnt1 - 1) / 3;
            cnt1 += dif * 2;
            cnt2 -= dif;
            ans = min(ans, max(cnt1 * 2 - 1, cnt2 * 2));
            if (cnt2 > 0){
                cnt1 += 2;
                --cnt2;
                ans = min(ans, max(cnt1 * 2 - 1, cnt2 * 2));
            }
        }
        printf("%lld\n", ans);
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif

    int n, k;
    scanf("%d %d", &n, &k);
    vector<long long> b(n);
    for (auto &it : b) {
        scanf("%lld", &it);
    }
    
    vector<long long> closed(n);
    long long sum = 0, cnt = 0, ans = 0;
    for (int i = n - 1; i >= 0; --i) {
        sum -= cnt;
        cnt -= closed[i];
        b[i] -= sum;
        if (b[i] <= 0) {
            continue;
        }
        int el = min(i + 1, k);
        long long need = (b[i] + el - 1) / el;
        sum += need * el;
        cnt += need;
        ans += need;
        if (i - el >= 0) {
            closed[i - el] += need;
        }
    }
    
    printf("%lld\n", ans);
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++) 

int main(){
    cin.tie(0);
	iostream::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<string> s(3);
	forn(i, 3) cin >> s[i];
	vector<int> pr(n + 1);
	forn(i, n){
		pr[i + 1] += pr[i];
		forn(j, 3) pr[i + 1] += (s[j][i] == '1');
	}
	
	vector<int> p(3 * n), rk(3 * n, 1);
	iota(p.begin(), p.end(), 0);
	function<int(int)> getp;
	getp = [&](int a) -> int {
		return a == p[a] ? a : p[a] = getp(p[a]);
	};
	auto unite = [&](int a, int b) -> bool {
		a = getp(a), b = getp(b);
		if (a == b) return false;
		if (rk[a] < rk[b]) swap(a, b);
		p[b] = a;
		rk[a] += rk[b];
		return true;
	};
	
	vector<int> prhe(n + 1), prve(n + 1);
	
	forn(j, n){
		forn(i, 2) if (s[i][j] == '1' && s[i + 1][j] == '1' && unite(i * n + j, (i + 1) * n + j))
			++prve[j + 1];
		forn(i, 3) if (j > 0 && s[i][j] == '1' && s[i][j - 1] == '1' && unite(i * n + j, i * n + (j - 1)))
			++prhe[j];
	}
	forn(i, n) prve[i + 1] += prve[i];
	forn(i, n) prhe[i + 1] += prhe[i];
	
	vector<int> nxt(n + 1, 0);
	for (int i = n - 1; i >= 0; --i)
		nxt[i] = (s[0][i] == '1' && s[1][i] == '0' && s[2][i] == '1' ? (nxt[i + 1] + 1) : 0);
	
	int m;
	cin >> m;
	forn(_, m){
		int l, r;
		cin >> l >> r;
		--l, --r;
		int non101 = l + nxt[l];
		if (non101 > r){
		    cout << "2\n";
		    continue;
		}
		int tot = pr[r + 1] - pr[non101];
		int in = (prve[r + 1] - prve[non101]) + (prhe[r] - prhe[non101]);
		int res = tot - in;
		if (non101 != l){
			if (s[0][non101] == '1' && s[1][non101] == '1' && s[2][non101] == '1');
			else if (s[0][non101] == '0' && s[2][non101] == '0') res += 2;
			else ++res;
		}
		cout << res << "\n";
	}
	
	return 0;
}

#include <bits/stdc++.h>     

using namespace std;

int n;
vector<int> lens;

long long sqr(int x)
{
    return x * 1ll * x;
}

long long eval_split(int len, int k)
{
    return sqr(len / k) * (k - len % k) + sqr(len / k + 1) * (len % k);
}

pair<int, long long> eval_segment(int len, long long bound)
{
    // only take options with value >= bound
    if(bound <= 2 || len == 1)
        return make_pair(len - 1, len);
    int lf = 0;
    int rg = len - 1;
    while(rg - lf > 1)
    {
        int mid = (lf + rg) / 2;
        if(eval_split(len, mid) - eval_split(len, mid + 1) >= bound)
            lf = mid;
        else
            rg = mid;    
    }
    return make_pair(lf, eval_split(len, lf + 1));
}

pair<int, long long> eval_full(long long bound)
{
    pair<int, long long> ans;
    for(auto x : lens)
    {
        pair<int, long long> cur = eval_segment(x, bound);
        ans.first += cur.first;
        ans.second += cur.second;
    }
    return ans;
}

int main()
{
    scanf("%d", &n);
    int pr = 0;
    for(int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        lens.push_back(x - pr);
        pr = x;
    }
    long long w;
    scanf("%lld", &w);
    long long lf = 0ll;
    long long rg = (long long)(1e18) + 43;
    if(eval_full(rg).second <= w)
    {
        cout << 0 << endl;
        return 0;
    }
    while(rg - lf > 1)
    {
        long long mid = (lf + rg) / 2;
        pair<int, long long> res = eval_full(mid);
        if(res.second <= w)
            lf = mid;
        else
            rg = mid;
    }   
    pair<int, long long> resL = eval_full(lf);
    pair<int, long long> resR = eval_full(rg);
    assert(resL.second <= w && resR.second > w);
    long long change = (resR.second - resL.second) / (resR.first - resL.first);
    cout << resL.first + (w - resL.second) / change << endl;
}