Please note the non-standard memory limit.

There are n problems numbered with integers from 1 to n. i-th problem has the complexity c_i = 2^i, tag tag_i and score s_i.

After solving the problem i it's allowed to solve problem j if and only if IQ < |c_i - c_j| and tag_i ≠ tag_j. After solving it your IQ changes and becomes IQ = |c_i - c_j| and you gain |s_i - s_j| points.

Any problem can be the first. You can solve problems in any order and as many times as you want.

Initially your IQ = 0. Find the maximum number of points that can be earned.

Input

The first line contains a single integer t (1 ≤ t ≤ 100) — the number of test cases. 

The first line of each test case contains an integer n (1 ≤ n ≤ 5000) — the number of problems.

The second line of each test case contains n integers tag_1, tag_2, …, tag_n (1 ≤ tag_i ≤ n) — tags of the problems.

The third line of each test case contains n integers s_1, s_2, …, s_n (1 ≤ s_i ≤ 10^9) — scores of the problems.

It's guaranteed that sum of n over all test cases does not exceed 5000.

Output

For each test case print a single integer — the maximum number of points that can be earned.

Example

Input


5
4
1 2 3 4
5 10 15 20
4
1 2 1 2
5 10 15 20
4
2 2 4 1
2 8 19 1
2
1 1
6 9
1
1
666


Output


35
30
42
0
0

Note

In the first test case optimal sequence of solving problems is as follows: 

  1. 1 → 2, after that total score is 5 and IQ = 2 
  2. 2 → 3, after that total score is 10 and IQ = 4 
  3. 3 → 1, after that total score is 20 and IQ = 6 
  4. 1 → 4, after that total score is 35 and IQ = 14 



In the second test case optimal sequence of solving problems is as follows: 

  1. 1 → 2, after that total score is 5 and IQ = 2 
  2. 2 → 3, after that total score is 10 and IQ = 4 
  3. 3 → 4, after that total score is 15 and IQ = 8 
  4. 4 → 1, after that total score is 35 and IQ = 14 



In the third test case optimal sequence of solving problems is as follows: 

  1. 1 → 3, after that total score is 17 and IQ = 6 
  2. 3 → 4, after that total score is 35 and IQ = 8 
  3. 4 → 2, after that total score is 42 and IQ = 12

Difficulty: VERY_HARD
Tags: Number theory

Bit manipulation

Graph algorithms

Dynamic programming
Skill types: Dynamic programming

Bit manipulation

Starter code:

Solutions:
def nr():
	return int(input())

def nrs():
	return [int(i) for i in input().split()]

def f(n, t, s):
	d = [0] * n
	for i in range(1, n):
		for j in range(i - 1, -1, -1):
			if t[i] == t[j]:
				continue
			sc = abs(s[i] - s[j])
			(d[i], d[j]) = (max(d[i], d[j] + sc), max(d[j], d[i] + sc))
	return max(d)
for _ in range(nr()):
	n = nr()
	t = nrs()
	s = nrs()
	print(f(n, t, s))


from sys import stdin
input = stdin.readline

def D708():
	t = int(input())
	for _ in range(t):
		n = int(input())
		tags = list(map(int, input().split()))
		s = list(map(int, input().split()))
		dp = [0] * n
		for j in range(1, n):
			for i in range(j - 1, -1, -1):
				if tags[i] != tags[j]:
					score = abs(s[i] - s[j])
					(dpi, dpj) = (dp[i], dp[j])
					dp[i] = max(dp[i], dpj + score)
					dp[j] = max(dp[j], dpi + score)
		print(max(dp))
D708()


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	dp = [0] * n
	for i in range(n):
		for j in range(i - 1, -1, -1):
			if A[i] == A[j]:
				continue
			s = abs(B[i] - B[j])
			(dp[i], dp[j]) = (max(dp[i], dp[j] + s), max(dp[j], dp[i] + s))
	print(max(dp))


import os, sys, heapq as h, time
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getInt():
	return int(input())

def getStrs():
	return input().split()

def getInts():
	return list(map(int, input().split()))

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def isInt(s):
	return '0' <= s[0] <= '9'
MOD = 10 ** 9 + 7

def solve():
	N = getInt()
	tags = getInts()
	S = getInts()
	ans = 0
	dp = [0] * N
	for i in range(N):
		for j in range(i - 1, -1, -1):
			if tags[i] != tags[j]:
				tmp = dp[j]
				dp[j] = max(dp[j], dp[i] + abs(S[j] - S[i]))
				dp[i] = max(dp[i], tmp + abs(S[j] - S[i]))
	return max(dp)
for _ in range(getInt()):
	print(solve())


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	n = int(input())
	Tag = list(map(int, input().split()))
	S = list(map(int, input().split()))
	DP = [0] * n
	ANS = 0
	for i in range(1, n):
		MAX = 0
		for j in range(i - 1, -1, -1):
			temp = DP[j]
			if Tag[j] != Tag[i]:
				DP[i] = max(DP[i], DP[j] + abs(S[i] - S[j]))
				DP[j] = max(DP[j], MAX + abs(S[j] - S[i]))
				MAX = max(MAX, temp + abs(S[i] - S[j]))
	print(max(DP))


def solve():
	n = int(input())
	c = list(map(int, input().split()))
	s = list(map(int, input().split()))
	ans = 0
	dp = [0] * n
	for i in range(n):
		for j in range(i - 1, -1, -1):
			if c[i] != c[j]:
				tmp = dp[j]
				dp[j] = max(dp[j], dp[i] + abs(s[i] - s[j]))
				dp[i] = max(dp[i], tmp + abs(s[i] - s[j]))
	return max(dp)
for i in range(int(input())):
	print(solve())


from sys import stdin
from bisect import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(t,) = gil()
for _ in range(t):
	(n,) = gil()
	tag = gil()
	s = gil()
	ans = [0] * n
	for i in range(1, n):
		for j in reversed(range(i)):
			if tag[i] == tag[j]:
				continue
			(ai, aj, x) = (ans[i], ans[j], abs(s[i] - s[j]))
			(ans[i], ans[j]) = (max(ans[i], aj + x), max(ans[j], ai + x))
	print(max(ans))