You are given two lists of segments $[al_1, ar_1], [al_2, ar_2], \dots, [al_n, ar_n]$ and $[bl_1, br_1], [bl_2, br_2], \dots, [bl_n, br_n]$.

Initially, all segments $[al_i, ar_i]$ are equal to $[l_1, r_1]$ and all segments $[bl_i, br_i]$ are equal to $[l_2, r_2]$.

In one step, you can choose one segment (either from the first or from the second list) and extend it by $1$. In other words, suppose you've chosen segment $[x, y]$ then you can transform it either into $[x - 1, y]$ or into $[x, y + 1]$.

Let's define a total intersection $I$ as the sum of lengths of intersections of the corresponding pairs of segments, i.e. $\sum\limits_{i=1}^{n}{\text{intersection_length}([al_i, ar_i], [bl_i, br_i])}$. Empty intersection has length $0$ and length of a segment $[x, y]$ is equal to $y - x$.

What is the minimum number of steps you need to make $I$ greater or equal to $k$?


-----Input-----

The first line contains the single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $1 \le k \le 10^9$) — the length of lists and the minimum required total intersection.

The second line of each test case contains two integers $l_1$ and $r_1$ ($1 \le l_1 \le r_1 \le 10^9$) — the segment all $[al_i, ar_i]$ are equal to initially.

The third line of each test case contains two integers $l_2$ and $r_2$ ($1 \le l_2 \le r_2 \le 10^9$) — the segment all $[bl_i, br_i]$ are equal to initially.

It's guaranteed that the sum of $n$ doesn't exceed $2 \cdot 10^5$.


-----Output-----

Print $t$ integers — one per test case. For each test case, print the minimum number of step you need to make $I$ greater or equal to $k$.


-----Example-----
Input
3
3 5
1 2
3 4
2 1000000000
1 1
999999999 999999999
10 3
5 10
7 8

Output
7
2000000000
0



-----Note-----

In the first test case, we can achieve total intersection $5$, for example, using next strategy:   make $[al_1, ar_1]$ from $[1, 2]$ to $[1, 4]$ in $2$ steps;  make $[al_2, ar_2]$ from $[1, 2]$ to $[1, 3]$ in $1$ step;  make $[bl_1, br_1]$ from $[3, 4]$ to $[1, 4]$ in $2$ steps;  make $[bl_2, br_2]$ from $[3, 4]$ to $[1, 4]$ in $2$ steps.  In result, $I = \text{intersection_length}([al_1, ar_1], [bl_1, br_1]) + \text{intersection_length}([al_2, ar_2], [bl_2, br_2]) + \\ + \text{intersection_length}([al_3, ar_3], [bl_3, br_3]) = 3 + 2 + 0 = 5$

In the second test case, we can make $[al_1, ar_1] = [0, 1000000000]$ in $1000000000$ steps and $[bl_1, br_1] = [0, 1000000000]$ in $1000000000$ steps.

In the third test case, the total intersection $I$ is already equal to $10 > 3$, so we don't need to do any steps.

Difficulty: interview

Starter code:

Solutions:
t = int(input())

for _ in range(t):
    n, k = [int(x) for x in input().split()]
    l1, r1 = [int(x) for x in input().split()]
    l2, r2 = [int(x) for x in input().split()]
    if l1 > l2:
        l1, r1, l2, r2 = l2, r2, l1, r1

    if l2 < r1:
        # they already intersect.
        start = (min(r1, r2) - max(l1, l2))*n
        if start >= k:
            print(0)
            continue
        cheap = n*(max(r1, r2) - min(l1, l2)) - start
        if start + cheap >= k:
            print(k - start)
            continue
        else:
            print(cheap + (k - start - cheap)*2)
            continue

    # they do not intersect yet.
    best = 10**100
    cost_sf = 0
    intersection_sf = 0
    for j in range(n):
        # compute price using j-th interval as the last.
        cost_sf += l2 - r1
        cheap = r2 - l1
        if intersection_sf + cheap >= k:
            best = min(best, cost_sf + max((k - intersection_sf), 0))

        intersection_sf += cheap
        cost_sf += cheap
        
        best = min(best, cost_sf + max((k - intersection_sf)*2, 0))
    print(best)



def inter(l1, r1, l2, r2):
    l = max(l1,l2)
    r = min(r1,r2)
    return max(r - l, 0)
def solve():
    n, k = map(int,input().split())
    al, ar = map(int,input().split())
    bl, br = map(int,input().split())
    res = inter(al,ar,bl,br) * n
    goodt = max(ar, br) - min(al,bl) - inter(al,ar,bl,br)
    minhodi = 1000000000000
    hodi = 0
    to_soed = max(0, max(al,bl) - min(ar, br))
    if res >= k:
        print(0)
        return 0
    for i in range(n):
        hodi += to_soed
        ineed = k - res
        if goodt >= ineed:
            hodi += ineed
            minhodi = min(minhodi, hodi)
            break
        hodi += goodt
        res += goodt
        minhodi = min(hodi + (k - res) * 2, minhodi)
    print(minhodi)
for i in range(int(input())):
    solve()

import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')


def solve():
    n, k = nm()
    a, b = nm()
    c, d = nm()
    if d < b:
        a, b, c, d = c, d, a, b
    if a <= c <= b:
        cur = (b - c) * n
        if (d - a) * n > k:
            print(max(k - cur, 0))
        else:
            ans = (d - a) * n - cur
            print(ans + (k - (d - a) * n) * 2)
    elif c < a:
        cur = (b - a) * n
        if (d - c) * n > k:
            print(max(k - cur, 0))
        else:
            ans = (d - c) * n - cur
            print(ans + (k - (d - c) * n) * 2)
    else:
        ans = 10**18
        cur = 0
        for i in range(n):
            cur += c - b
            if k > d - a:
                k -= d - a
                cur += d - a
            else:
                cur += k
                k -= k
            ans = min(ans, cur + k * 2)
        print(ans)
    return


# solve()

T = ni()
for _ in range(T):
    solve()


for _ in range(int(input())):
    n,k=list(map(int,input().split()))
    l1,r1=list(map(int,input().split()))
    l2,r2=list(map(int,input().split()))
    if l1>l2:
        l1,r1,l2,r2=l2,r2,l1,r1

    if l2>r1:
        ans=float("inf")
        for i in range(1,n+1):
            temp=i*(l2-r1)
            limit=(r2-l1)*i
            if k<=limit:
                temp+=k
                ans=min(ans,temp)
            else:
                temp+=limit
                K=k-limit
                temp+=2*K
                ans=min(ans,temp)
        print(ans)
    else:
        count=n*(min(r1,r2)-l2)
        res=0
        if count>k:
            print(res)
            continue
        b=max(r2,r1)-min(l2,l1)-(min(r1,r2)-l2)
        for i in range(n):
            if k-count<=b:
                res+=k-count
                break
            else:
                res+=b
                count+=b
        else:
            res+=(k-count)*2
        print(res)


from sys import stdin

tt = int(stdin.readline())

for loop in range(tt):

    #don't

    n,k = map(int,stdin.readline().split() )
    l1,r1 = map(int,stdin.readline().split())
    l2,r2 = map(int,stdin.readline().split())

    #don't
    if l1 >= r2 or l2 >= r1:
        ans = float("inf")
        for usenum in range(1,n+1):

            if max(abs(l1-r2),abs(l2-r1))*usenum >= k:
                ans = min(ans , min(abs(l1-r2),abs(l2-r1))*usenum + k)
            else:
                rem = k - max(abs(l1-r2),abs(l2-r1))*usenum
                ans = min(ans , min(abs(l1-r2),abs(l2-r1))*usenum + max(abs(l1-r2),abs(l2-r1))*usenum + rem*2)
        print (ans)

    else:
        ans = float("inf")
        over = min(r1-l1 , r2-l2 , r1-l2 , r2-l1)
        usenum = n

        if over * usenum >= k:
            print (0)
            continue
        k -= over * usenum
        useable = max(r1-l1 , r2-l2 , r1-l2 , r2-l1) - over

        if useable * usenum >= k:
            print (k)
            continue
        else:
            rem = k - useable * usenum
            print (useable * usenum + rem*2)

for _ in range(int(input())):
    n, k = list(map(int, input().split()))
    l_1, r1 = list(map(int, input().split()))
    l_2, r2 = list(map(int, input().split()))
    if r1 < l_2:
        pre_steps = l_2 - r1
    elif l_1 > r2:
        pre_steps = l_1 - r2
    else:
        pre_steps = 0
    if pre_steps:
        easy_steps = r1 + r2 - l_1 - l_2 + pre_steps
    else:
        easy_steps = abs(l_1 - l_2) + abs(r1 - r2)
        k -= (min(r1, r2) - max(l_1, l_2)) * n
    ans = pre_steps * n + k * 2
    # for n1 in max(1, k // easy_steps), min(1, (k - 1) // easy_steps + 1):
    for n1 in range(1, n + 1):
        cur_ans = pre_steps * n1
        if easy_steps * n1 < k:
            cur_ans += k * 2 - easy_steps * n1
        else:
            cur_ans += k
        ans = min(ans, cur_ans)
    if k <= 0:
        ans = 0
    print(ans)


t = int(input())

for _ in range(t):
    n, k = list(map(int, input().split()))
    
    l1, r1 = list(map(int, input().split()))
    l2, r2 = list(map(int, input().split()))
    
    if l1 > l2:
        l1, r1, l2, r2 = l2, r2, l1, r1
        
    if l2 <= r1: # already overlapping
        per_interval = abs(l1-l2) + abs(r1-r2)
        already_overlap = min(r1, r2) - max(l1, l2)
        k -= already_overlap * n
        k = max(k, 0)
        if per_interval * n >= k:
            print(k)
            continue
        cost = per_interval * n
        cost += 2 * (k - cost)
        print(cost)
        continue
    
    # not overlapping
    
    diff = l2 - r1
    per_interval = r2 - l1
    
    if per_interval >= k:
        print(diff + k)
        continue
    
    cost = diff + per_interval
    #print(diff, per_interval)
    rem_n = n-1
    rem_k = k - per_interval
    while rem_n and diff < per_interval and rem_k >= per_interval:
        rem_n -= 1
        rem_k -= per_interval
        cost += diff + per_interval
    
    if rem_n and diff < per_interval:
        cost_from_new = diff + rem_k
        cost_from_cur = 2 * rem_k
        cost += min(cost_from_new, cost_from_cur)
    else:
        cost += 2 * rem_k
    print(cost)


import sys
input = sys.stdin.readline
T = int(input())

for testcase in range(1,T+1):
    n,k = list(map(int,input().split()))
    a,b = list(map(int,input().split()))
    s,t = list(map(int,input().split()))

    if a > s:
        a,s = s,a
        b,t = t,b
    """ a <= s """


    if s <= b and n*(min(b,t)-s) >= k:
        print(0)
    else:
        if s <= b:
            now = n*(min(b,t)-s)
            w = n*((s-a) + abs(t-b))
            if now + w >= k:
                print(k-now)
            else:
                now += w
                print(w + (k-now)*2)
        else:
            if (t-a) >= k:
                print(s-b+k)
                
            else:
                res = 10**20
                for i in range(1,n+1):
                    tmp = i*(s-b)
                    if i*(t-a) >= k:
                        tmp += k
                        #print("b",i,a,b,s,t)
                    else:
                        tmp += i*(t-a) + (k-i*(t-a))*2
                    res = min(res,tmp)
                    #print("a",i,tmp)
                print(res)



t = int(input())
for _ in range(t):
    n, k = list(map(int, input().split()))
    l1, r1 = list(map(int, input().split()))
    l2, r2 = list(map(int, input().split()))
    mr = max(r1, r2) - min(l1, l2)
    step = 2 * mr - (r1 - l1) - (r2 - l2)
    over = max(0, min(r1, r2) - max(l1, l2))
    dis = (max(l1, l2) - min(r1, r2)) if over == 0 else 0
    k = k - over * n
    if k <= 0:
        print(0)
        continue
    mr -= over
    res = 0
    if k <= mr:
        res = dis + k
    elif mr * n >= k:
        cnt = k // mr
        r = k % mr
        res += cnt * step
        if r > dis:
            res += dis + r
        else:
            res += 2 * r
    else:
        res += n * step + (k - mr * n) * 2
    print(res)


import sys
input = sys.stdin.readline
for f in range(int(input())):
    n,k=map(int,input().split())
    l1,r1=map(int,input().split())
    l2,r2=map(int,input().split())
    intersect=False
    if l1>=l2 and l1<=r2:
        intersect=True
    if r1>=l2 and r1<=r2:
        intersect=True
    if l2>=l1 and l2<=r1:
        intersect=True
    if r2>=l1 and r2<=r1:
        intersect=True
    if intersect:
        l=min(l1,l2)
        r=max(r1,r2)
        totlen=r-l
        intlen=(r2-l2)+(r1-l1)-totlen
        if n*intlen>=k:
            print(0)
        else:
            if n*totlen>=k:
                print(k-n*intlen)
            else:
                s=n*(totlen-intlen)
                k-=n*totlen
                print(s+2*k)
    else:
        l=min(l1,l2)
        r=max(r1,r2)
        totlen=r-l
        dist=totlen-(r2-l2)-(r1-l1)
        s=0
        i=0
        while k>0 and i<n:
            i+=1
            s+=dist
            if k<=totlen:
                s+=k
                k=0
            else:
                k-=totlen
                s+=totlen
                if k<dist:
                    s+=2*k
                    k=0
        if k>0:
            s+=2*k
        print(s)