Alice and Bob are walking on an infinite straight street. Initially, both are at the position $X=0$ and they start walking in the direction of increasing $X$. After $N$ seconds, they stop. Let's denote Alice's speed and Bob's speed during the $i$-th of these seconds by $A_i$ and $B_i$ respectively.
Sometimes, Alice and Bob walk together, i.e. with the same speed side by side. Let's define the weird distance as the total distance they walk this way. Find this weird distance.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.
- The third line contains $N$ space-separated integers $B_1, B_2, \ldots, B_N$.

-----Output-----
For each test case, print a single line containing one integer ― the total weird distance. It can be proved that this distance is an integer.

-----Constraints-----
- $1 \le T \le 20$
- $1 \le N \le 10^5$
- $1 \le A_i \le 10^5$ for each valid $i$
- $1 \le B_i \le 10^5$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (30 points): $1 \le N \le 1,000$
Subtask #2 (70 points): original constraints

-----Example Input-----
3
4
1 3 3 4
1 2 4 4
2
2 3
3 2
2
3 3
3 3

-----Example Output-----
5
0
6

-----Explanation-----
Example case 1:
- Alice and Bob walk side by side during the first second, from $X=0$ to $X=1$.
- Then, Alice starts walking faster than Bob, so they do not walk side by side during second $2$. At the end of second $2$, Alice is at $X=4$, while Bob is at $X=3$.
- During the next second, they again do not walk side by side, but Bob walks faster, so they both end up at $X=7$.
- During the last second, they both walk side by side and the distance they walk is $4$.
- Alice and Bob walk side by side during the $1$-st and $4$-th second and the total weird distance they travel is $1+4=5$.
Example case 2:
- First, Alice walks with speed $2$ and Bob walks with speed $3$, so they do not walk side by side. Alice ends up at $X=2$, while Bob ends up at $X=3$ at the end of the $1$-st second.
- Then, Alice walks with speed $3$ and Bob walks with speed $2$, so they do not walk side by side either.
- Although Alice and Bob both end up at $X=5$ at the end of the $2$-nd second, the weird distance is $0$.
Example case 3: We can see that Alice and Bob always walk together, so the weird distance is $3+3=6$.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
for tc in range(int(input())):
 
 n = int(input())
 
 li1 = list(map(int,input().split(' ')))
 li2 = list(map(int,input().split(' ')))
 walk = 0
 sum1 = 0 
 sum2 = 0
 for i in range(n):
  if li1[i] == li2[i] and sum1 == sum2:
   walk += li1[i]
  sum1 += li1[i]
  sum2 += li2[i]
 print(walk)

for _ in range(int(input())):
 n = int(input())

 arr1 = list(map(int,input().split()))
 arr2 = list(map(int,input().split()))
 res=0
 presum1=0
 presum2=0
 for i in range(n):
  if arr1[i]== arr2[i] and presum1==presum2 :
   
   res+=arr1[i]
  presum1+=arr1[i]
  presum2 +=arr2[i]
  
 print(res)

   



 




 




for _ in range(int(input())):
 n = int(input())

 arr1 = list(map(int,input().split()))
 arr2 = list(map(int,input().split()))
 res=0
 for i in range(n):
  if arr1[i]== arr2[i] and sum(arr1[:i])==sum(arr2[:i]):
   res+=arr1[i]
 print(res)

   



 




 


# cook your dish here


# cook your dish here
for i in range(int(input())):
 t = int(input())
 Alice = list(map(int,input().split()))
 Bob = list(map(int,input().split()))
 tot_Alice = 0
 tot_Bob = 0
 total = []
 for j,k in zip(Alice,Bob):
  if (tot_Alice==tot_Bob) and (j==k):
   total.append(j)
   tot_Alice += j 
   tot_Bob += k 
  else:
   tot_Alice += j 
   tot_Bob += k 
 print(sum(total))

# cook your dish here
def walk(n,m,o):
 a=0
 b=0
 tot=0
 for i in range(n):
  if((m[i]==o[i]) and (a==b)):
   tot+=m[i]
  a+=m[i]
  b+=o[i]
 return tot
t=int(input())
for i in range(t):
 n=int(input())
 m=list(map(int, input().split()))
 o=list(map(int, input().split()))
 print(walk(n,m,o))

for _ in range(int(input())):
 n=int(input())
 a=[int(x) for x in input().split()]
 b=[int(x) for x in input().split()]
 an=0
 pa,pb=0,0
 for i in range(n):
  if a[i]==b[i] and pa==pb:
   an+=a[i]
  pa+=a[i]
  pb+=b[i]
 print(an)

T = int(input())
ans = []

for _ in range(T):
 N = int(input())
 A = [int(i) for i in input().split()]
 B = [int(i) for i in input().split()]

 xa = 0
 xb = 0
 distance = 0

 for i in range(N):
  if(xa==xb and A[i]==B[i]):
   distance += A[i]
  xa += A[i]
  xb += B[i]

 ans.append(distance)

for i in ans:
 print(i)

try:
 for i in range(int(input())):
  n=int(input())
  a=list(map(int,input().split()))
  b=list(map(int,input().split()))
  sa=0
  sb=0
  ans=0
  # if n==1:
  #   if ai[0] == bi[0]:
  #       print(ai[0])
  #   else:
  #       print(0)
  # else :
  #   for i in range(0,n):
  #       if  i==0 :
  #           if ai[i]==bi[i]:
  #               sa=sa+ai[i]
  #               sb=sb+bi[i]
  #               ans=ans+ai[i]
  #       elif sum(ai[:i]) == sum(bi[:i]) :
  #           if ai[i] == bi[i]:
  #               ans=ans+ai[i]
  #       else:
  #           sa=sa+ai[i]
  #           sb=sb+bi[i]
  #   print(ans)

  for i in range(0,n):
   # if i == 0:
   #   if ai[i] == bi[i]:
   #       sa=sa+ai[i]
   #       sb=sb+bi[i]
   #       ans=ans+ai[i]
   sa=sa+a[i]
   sb=sb+b[i]
   if sa==sb and a[i] == b[i]:
    ans=ans+a[i]

  print(ans)
except:
 pass

try:
 for i in range(int(input())):
  n=int(input())
  ai=list(map(int,input().split()))
  bi=list(map(int,input().split()))
  sa=0
  sb=0
  ans=0
  # if n==1:
  #   if ai[0] == bi[0]:
  #       print(ai[0])
  #   else:
  #       print(0)
  # else :
  #   for i in range(0,n):
  #       if  i==0 :
  #           if ai[i]==bi[i]:
  #               sa=sa+ai[i]
  #               sb=sb+bi[i]
  #               ans=ans+ai[i]
  #       elif sum(ai[:i]) == sum(bi[:i]) :
  #           if ai[i] == bi[i]:
  #               ans=ans+ai[i]
  #       else:
  #           sa=sa+ai[i]
  #           sb=sb+bi[i]
  #   print(ans)

  for i in range(0,n):
   # if i == 0:
   #   if ai[i] == bi[i]:
   #       sa=sa+ai[i]
   #       sb=sb+bi[i]
   #       ans=ans+ai[i]
   if ai[i] == bi[i]:
    if sum(ai[:i]) == sum(bi[:i]):
     ans=ans+ai[i]
    else:
     sa=sa+ai[i]
     sb=sb+bi[i]
   else:
    sa=sa+ai[i]
    sb=sb+bi[i]

  print(ans)
except:
 pass

try:
 for i in range(int(input())):
  n=int(input())
  ai=list(map(int,input().split()))
  bi=list(map(int,input().split()))
  sa=0
  sb=0
  ans=0
  if n==1:
   if ai[0] == bi[0]:
    print(ai[0])
   else:
    print(0)
  else :
   for i in range(0,n):
    if i==0 :
     if ai[i]==bi[i]:
      sa=sa+ai[i]
      sb=sb+bi[i]
      ans=ans+ai[i]
    elif sum(ai[:i]) == sum(bi[:i]) :
     if ai[i] == bi[i]:
      ans=ans+ai[i]
    else:
     sa=sa+ai[i]
     sb=sb+bi[i]
   print(ans)
except:
 pass

try:
 for i in range(int(input())):
  n=int(input())
  ai=list(map(int,input().split()))
  bi=list(map(int,input().split()))
  sa=0
  sb=0
  ans=0
  if n==1:
   if ai[0] == bi[0]:
    print(ai[0])
   else:
    print(0)
  else :
   for i in range(0,n):
    if ai[i]==bi[i] and i==0:
     sa=sa+ai[i]
     sb=sb+bi[i]
     ans=ans+ai[i]
    elif sum(ai[:i]) == sum(bi[:i]) and ai[i] ==bi[i]:
     ans=ans+ai[i]
    else:
     sa=sa+ai[i]
     sb=sb+bi[i]
   print(ans)
except:
 pass

for _ in range(int(input())):
 n = int(input())
 a = list(map(int,input().split()))
 b = list(map(int,input().split()))
 s = 0
 s1 = 0
 s2 = 0
 for i in range(len(a)):
  s1+=a[i]
  s2+=b[i]
  if s1==s2 and a[i]==b[i]:
   s+=a[i]
 print(s)


# cook your dish here
t=int(input())
while(t>0):
 n=int(input())
 l1=[int(x) for x in input().split()]
 l2=[int(x) for x in input().split()]
 s=0
 s1=0
 s2=0
 for i in range(n):
  s1=s1+l1[i]
  s2=s2+l2[i]
  if(s1==s2 and l1[i]==l2[i]):
   s=s+l1[i]
 print(s)
 t=t-1

for _ in range(int(input())):
 n=int(input())
 a=list(map(int,input().split()))
 ra=[0]*n
 x=0
 for i in range(n):
  ra[i]=x+a[i]
  x=ra[i]
 b=list(map(int,input().split()))
 rb=[0]*n
 y=0
 for i in range(n):
  rb[i]=y+b[i]
  y=rb[i]
 c=f=0
 if ra[0]==rb[0]:
  c=a[0]
 for i in range(1,n):
  if ra[i-1]==rb[i-1] and a[i]==b[i]:
   c+=a[i]
 print(c)
 


t= int(input())
for i in range(t):
 n = int(input())
 a1 = list(map(int,input().split()))
 b1 = list(map(int,input().split()))
 sum1 = 0
 sum2 = 0
 answer = 0
 for j in range(n) :
  if (sum1 == sum2) and (a1[j]==b1[j]):
   answer+=a1[j]
  sum1 = sum1+a1[j]
  sum2 = sum2+b1[j]
  
 print(answer)

# cook your dish here
t = int(input())
for _ in range(t):
 n = int(input())
 a = list(map(int, input().split()))
 b = list(map(int, input().split()))
 dist = 0
 x = 0
 y = 0
 for i in range(n):
  x = x + a[i]
  y = y + b[i]
  if a[i]==b[i] and x==y:
   dist = dist + a[i]
 print(dist)

# cook your dish here
for i in range(int(input())):
 n = int(input())
 a = list(map(int,input().split()))
 b = list(map(int,input().split()))
 s1=0;s2 =0;ans =0
 for i in range(n):
  if a[i]==b[i] and s1==s2:
   ans+=a[i]
  s1+=a[i]
  s2+=b[i]
 print(ans)


n=int(input())
for _ in range(n): 
 a=int(input())
 l=[int(x) for x in input().split()]
 l1=[int(x) for x in input().split()]
 s1=0
 s2=0
 ans=0
 for i in range(a): 
  if l[i]==l1[i] and s1==s2: 
   s1+=l[i]
   s2+=l1[i]
   ans+=l[i]
  else: 
   s1+=l[i]
   s2+=l1[i]
 print(ans)
 
   


for _ in range(int(input())):
 n, sm1, sm2, smf = int(input()), 0, 0, 0
 l1, l2 = list(map(int, input().split())), list(map(int, input().split()))
 for i in range(n):
  if sm1==sm2 and l1[i]==l2[i]: smf+=l1[i]
  sm1+=l1[i]; sm2+=l2[i]
 print(smf)

for _ in range(int(input())):
 n = int(input())
 a = list(map(int,input().split()))
 b = list(map(int,input().split()))
 c = d = r = 0
 for i in range(n):
  if c==d and a[i]==b[i]:
   r+=a[i]
  c+=a[i]
  d+=b[i]
 print(r)

for _ in range(int(input())):
 n = int(input())
 a = input().split()
 b = input().split()
 Sum = 0
 suma = 0
 sumb = 0
 for i in range(len(a)):
  if i == 0:
   suma += int(a[i])
   sumb += int(b[i])
   if suma == sumb:
    Sum += int(a[i])
  else:
   if suma == sumb:
    suma += int(a[i])
    sumb += int(b[i])
    if suma == sumb:
     Sum += int(a[i])
   else:
    suma += int(a[i])
    sumb += int(b[i])
 print(Sum)

# cook your dish here
for _ in range(int(input())):
 n=int(input())
 a=list(map(int,input().split()))
 b=list(map(int,input().split()))
 p=q=d=0
 for i in range(n):
  p+=a[i]
  q+=b[i]
  if(p==q and a[i]==b[i]):
   d+=a[i]
   #print(d)
 print(d)

# cook your dish here
t=int(input())
while(t>0):
 t-=1
 n=int(input())
 a=list(map(int,input().split()))
 b=list(map(int,input().split()))
 s=0
 da,db=0,0
 for i in range(n):
  da+=a[i]
  db+=b[i]
  if(a[i]==b[i] and da==db):
   s+=a[i]
 print(s)

for _ in range(int(input())):
 N = int(input())
 A = list(map(int, input().split()))
 B = list(map(int, input().split()))
 d1, d2 = [0], [0]
 s1 = s2 = ans = 0
 for i in range(N):
  s1 += A[i]
  s2 += B[i]
  d1.append(s1 * (i+1))
  d2.append(s2 * (i+1))
 #  print(d1, d2)
 for i in range(N):
  if (d1[i] == d2[i]) and (d1[i+1] == d2[i+1]):
   ans += A[i]
 print(ans)