Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

There are $N$ frogs (numbered $1$ through $N$) in a line. For each valid $i$, the $i$-th frog is initially at the position $i$, it has weight $W_{i}$, and whenever you hit its back, it jumps a distance $L_{i}$ to the right, i.e. its position increases by $L_{i}$. The weights of the frogs are pairwise distinct.

You can hit the back of each frog any number of times (possibly zero, not necessarily the same for all frogs) in any order. The frogs do not intefere with each other, so there can be any number of frogs at the same time at each position.

Your task is to sort the frogs in the increasing order of weight using the smallest possible number of hits. In other words, after all the hits are performed, then for each pair of frogs $(i, j)$ such that $W_{i} < W_{j}$, the position of the $i$-th frog should be strictly smaller than the position of the $j$-th frog. Find the smallest number of hits needed to achieve such a state.

------  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 $W_{1}, W_{2}, \ldots, W_{N}$.
The third line contains $N$ space-separated integers $L_{1}, L_{2}, \ldots, L_{N}$.

------  Output ------
For each test case, print a single line containing one integer ― the smallest number of times you need to hit the backs of the frogs.

------  Constraints ------
$1 ≤ T ≤ 2 \cdot 10^{4}$
$2 ≤ N ≤ 4$
$1 ≤ W_{i} ≤ N$ for each valid $i$
$1 ≤ L_{i} ≤ 5$ for each valid $i$
no two frogs have the same weight

------  Subtasks ------
Subtask #1 (50 points):
$T = 50$
$N = 2$

Subtask #2 (50 points): original constraints

----- Sample Input 1 ------ 
3

3

3 1 2

1 4 5

3

3 2 1

1 1 1

4

2 1 4 3

4 1 2 4
----- Sample Output 1 ------ 
3

6

5
----- explanation 1 ------ 
Example case 1: We can hit the back of the first frog three times.

Example case 2: We can hit the back of the first frog four times, then hit the back of the second frog two times.

Difficulty: MEDIUM
Tags: Sorting

Constructive algorithms

Ad-hoc
Skill types: Sorting

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = []
	for i in range(1, n + 1):
		l.append(a.index(i) + 1)
	ans = 0
	for i in range(1, n):
		if l[i - 1] < l[i]:
			continue
		else:
			while l[i - 1] >= l[i]:
				ans += 1
				l[i] += b[a.index(i + 1)]
	print(ans)


t = int(input())
while t:
	t -= 1
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	d = {}
	ans = 0
	for i in range(n):
		d[w[i]] = i
	for i in range(2, n + 1):
		if d[i] <= d[i - 1]:
			v = d[i - 1] - d[i]
			jump = l[d[i]]
			ind = (v + jump) // jump
			d[i] += jump * ind
			ans += ind
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	(d, s) = ({}, 0)
	for i in range(1, n + 1):
		d[i] = w.index(i)
	for i in range(2, n + 1):
		(t1, t2, t) = (d[i], d[i - 1], 0)
		if t1 <= t2:
			t = math.ceil((t2 + 1 - t1) / l[t1])
		s += t
		d[i] += t * l[t1]
	print(s)


for _ in range(int(input())):
	N = int(input())
	W = list(map(int, input().split()))
	L = list(map(int, input().split()))
	curr = W.index(1)
	count = 0
	for i in range(2, N + 1):
		ind = W.index(i)
		if ind > curr:
			curr = ind
			continue
		jump = L[ind]
		while ind <= curr:
			ind += jump
			count += 1
		curr = ind
	print(count)


for z in range(int(input())):
	n = int(input())
	w = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	m = min(w)
	j = w.index(m)
	c = 0
	for x in sorted(w):
		i = w.index(x)
		if i > j or x == m:
			j = i
			continue
		k = j - i + 1
		if k % l[i] == 0:
			c += k // l[i]
			j += 1
		else:
			c += 1 + k // l[i]
			j = i + (1 + k // l[i]) * l[i]
	print(c)


for t in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	if n == 2:
		if w[0] == 1:
			print(0)
		elif l[0] > 1:
			print(1)
		else:
			print(2)
	elif n == 3:
		c = 0
		p = w.index(1)
		q = w.index(2)
		r = w.index(3)
		l2 = l[q]
		l3 = l[r]
		while q <= p:
			q += l2
			c += 1
		while r <= q:
			r += l3
			c += 1
		print(c)
	else:
		c = 0
		p = w.index(1)
		q = w.index(2)
		r = w.index(3)
		s = w.index(4)
		l2 = l[q]
		l3 = l[r]
		l4 = l[s]
		while q <= p:
			q += l2
			c += 1
		while r <= q:
			r += l3
			c += 1
		while s <= r:
			s += l4
			c += 1
		print(c)


for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	(minp, ans) = (0, 0)
	for i in range(1, n + 1):
		p = w.index(i)
		if p > minp:
			minp = p + 1
			continue
		d = l[p]
		h = (minp - p) // d + 1 if (minp - p) % d else (minp - p) // d
		ans += h
		minp = p + h * d + 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	weight = list(map(int, input().split()))[:n]
	jump = list(map(int, input().split()))[:n]
	d = []
	for i in range(n):
		d.append((weight[i], i))
	order = sorted(d)
	y = order[0][1]
	count = 0
	order = dict(order)
	for item in list(order.keys())[1:]:
		x = order[item]
		l = jump[x]
		if y >= x:
			t = int((y - x) / l) + 1
			count += t
			y = t * l + x
		else:
			y = x
	print(count)


t = int(input())
for i in range(t):
	c = 0
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	d = {}
	for j in range(len(l1)):
		d[l1[j]] = [j + 1, l2[j]]
	for k in range(2, len(l1) + 1):
		while d[k][0] <= d[k - 1][0]:
			d[k][0] += d[k][1]
			c += 1
	print(c)


for i in range(int(input())):
	count = 0
	num = int(input())
	list1 = list(map(int, input().split()))
	list2 = list(map(int, input().split()))
	temp_d = dict()
	for i in range(len(list1)):
		temp_d[list1[i]] = [i + 1, list2[i]]
	for j in range(2, len(list1) + 1):
		while temp_d[j][0] <= temp_d[j - 1][0]:
			temp_d[j][0] += temp_d[j][1]
			count += 1
	print(count)


import math
n = int(input())
for eachcase in range(n):
	frogs = int(input())
	weight = list(map(int, input().split()))
	leaps = list(map(int, input().split()))
	hits = 0
	position = [0, 0, 0, 0, 0]
	posjumps = [0, 0, 0, 0, 0]
	for numbers in range(1, frogs + 1):
		position[weight[numbers - 1]] = numbers
		posjumps[weight[numbers - 1]] = leaps[numbers - 1]
	for index in range(2, frogs + 1):
		if position[index] <= position[index - 1]:
			hits += math.ceil((1 + position[index - 1] - position[index]) / posjumps[index])
			position[index] += math.ceil((1 + position[index - 1] - position[index]) / posjumps[index]) * posjumps[index]
	print(hits)


t = int(input())
for i in range(t):
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	temp = []
	for j in range(n):
		temp.append([w[j], j + 1, l[j]])
	temp.sort()
	ct = 0
	ind = 0
	for j in temp:
		index = j[1]
		jump = j[2]
		if index > ind:
			ind = index
			continue
		else:
			diff = ind - index
			z = diff // jump
			z = z + 1
			ct += z
			ind = index + z * jump
	print(ct)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	ind = {}
	s = 0
	for j in range(1, n + 1):
		ind[j] = w.index(j)
	for j in range(2, n + 1):
		temp1 = ind[j]
		temp2 = ind[j - 1]
		temp = 0
		if temp1 <= temp2:
			temp = math.ceil((temp2 + 1 - temp1) / l[temp1])
		s += temp
		ind[j] += temp * l[temp1]
	print(s)


def fun(arr, fun2):
	n = len(arr)
	lst = []
	for i in range(n):
		lst.append((arr[i], fun2[i], i))
	lst = sorted(lst, key=lambda x: x[0])
	ans = 0
	curr = lst[0][-1]
	for i in range(1, n):
		(w, jump, next) = lst[i]
		while next <= curr:
			next += jump
			ans += 1
		curr = next
	print(ans)
n = int(input())
for i in range(n):
	n = int(input())
	arr = list(map(int, input().split()))
	fun2 = list(map(int, input().split()))
	fun(arr, fun2)


from math import ceil

def solve(length, w, l):
	positions = dict()
	for i in range(length):
		positions[w[i]] = i

	def find(elem):
		return positions[elem]
	total_jumps = 0
	prev_pos = find(1)
	for weight in range(2, length + 1):
		cur_pos = find(weight)
		a = ceil((prev_pos - cur_pos + 1) / l[cur_pos])
		if a < 0:
			a = 0
		total_jumps += a
		prev_pos = cur_pos + a * l[cur_pos]
	return total_jumps

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		w = list(map(int, input().split(' ')))
		l = list(map(int, input().split(' ')))
		print(solve(N, w, l))
main()


for _ in range(int(input())):
	cnt = 0
	n = int(input())
	idx = list(map(int, input().split()))
	wgt = list(map(int, input().split()))
	d = dict()
	for i in range(len(idx)):
		d[idx[i]] = [i + 1, wgt[i]]
	for j in range(2, len(idx) + 1):
		while d[j][0] <= d[j - 1][0]:
			d[j][0] += d[j][1]
			cnt += 1
	print(cnt)


import math
t = int(input())
for i in range(t):
	a = int(input())
	w = list(map(int, input().split()))[:a]
	L = list(map(int, input().split()))[:a]
	index = {}
	ans = 0
	for i in range(1, len(w) + 1):
		index[i] = w.index(i)
	for i in range(2, len(w) + 1):
		val = 0
		val1 = index[i]
		val2 = index[i - 1]
		if val1 <= val2:
			val = math.ceil((val2 + 1 - val1) / L[val1])
		ans += val
		index[i] += val * L[val1]
	print(ans)


import math

def bubble_sort_efficient(array):
	size = len(array)
	for i in range(size - 1):
		swapped = False
		for j in range(0, size - i - 1):
			if array[j] > array[j + 1]:
				(array[j], array[j + 1]) = (array[j + 1], array[j])
				swapped = True
		if not swapped:
			break
	return array
test_cases = int(input())
for _ in range(test_cases):
	N = int(input())
	W = [int(inputs) for inputs in input().strip().split()]
	L = [int(inputs) for inputs in input().strip().split()]
	sorted_W = bubble_sort_efficient(W[:])
	index_after = W.index(sorted_W[0])
	count = 0
	for i in range(1, len(W)):
		index = W.index(sorted_W[i])
		if index > index_after:
			index_after = index
			continue
		jump_value = L[index]
		minimum_position = index_after - index + 1
		jump_required = math.ceil(minimum_position / jump_value)
		index_after = index + jump_required * jump_value
		count += jump_required
	print(count)


T = int(input())
for i in range(T):
	N = int(input())
	W = list(map(int, input().split()))
	L = list(map(int, input().split()))
	res = 0
	if N == 2:
		p = 0
		q = 1
		l1 = L[0]
		if W[0] > W[1]:
			while p <= q:
				p += l1
				res += 1
		print(res)
	elif N == 3:
		for j in range(N):
			if W[j] == 1:
				p = j
				l1 = L[j]
			elif W[j] == 2:
				q = j
				l2 = L[j]
			else:
				r = j
				l3 = L[j]
		while q <= p:
			q += l2
			res += 1
		while r <= q:
			r += l3
			res += 1
		print(res)
	elif N == 4:
		for j in range(N):
			if W[j] == 1:
				p = j
				l1 = L[j]
			elif W[j] == 2:
				q = j
				l2 = L[j]
			elif W[j] == 3:
				r = j
				l3 = L[j]
			else:
				s = j
				l4 = L[j]
		while q <= p:
			q += l2
			res += 1
		while r <= q:
			r += l3
			res += 1
		while s <= r:
			s += l4
			res += 1
		print(res)


T = int(input())
for i in range(T):
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	count = 0
	d = dict()
	for i in range(0, len(w)):
		d[w[i]] = [i + 1, l[i]]
	for j in range(2, len(w) + 1):
		while d[j][0] <= d[j - 1][0]:
			d[j][0] += d[j][1]
			count += 1
	print(count)


def solve(l, idi, wei):
	cnt = 0
	d = dict()
	for i in range(0, len(idi)):
		d[idi[i]] = [i + 1, wei[i]]
	for j in range(2, len(idi) + 1):
		while d[j][0] <= d[j - 1][0]:
			d[j][0] += d[j][1]
			cnt += 1
	return cnt
test = int(input())
for _ in range(test):
	l = int(input())
	a = list(map(int, input().rstrip().split()))
	b = list(map(int, input().rstrip().split()))
	print(solve(l, a, b))


t = int(input())
for _ in range(t):
	cnt = 0
	n = int(input())
	idi = list(map(int, input().split()))
	wei = list(map(int, input().split()))
	d = dict()
	for i in range(0, len(idi)):
		d[idi[i]] = [i + 1, wei[i]]
	for j in range(2, len(idi) + 1):
		while d[j][0] <= d[j - 1][0]:
			d[j][0] += d[j][1]
			cnt += 1
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	d = {}
	jump = 0
	for i in range(n):
		d[w[i]] = i + 1
	for i in range(2, n + 1):
		a = l[d[i] - 1]
		while d[i - 1] >= d[i]:
			d[i] += a
			jump += 1
	print(jump)


import math
try:
	t = int(input())
	while t > 0:
		n = int(input())
		w = list(map(int, input().split()))
		l = list(map(int, input().split()))
		steps = 0
		dict1 = {}
		for i in range(1, n + 1):
			dict1[i] = w.index(i)
		for i in range(2, n + 1):
			t1 = dict1[i]
			t2 = dict1[i - 1]
			temp = 0
			if t1 <= t2:
				temp = math.ceil((t2 + 1 - t1) / l[t1])
			steps += temp
			dict1[i] += temp * l[t1]
		print(steps)
		t = t - 1
except:
	pass


def prog_name():
	n = int(input())
	w = list(map(int, input().split()))
	j = list(map(int, input().split()))
	i = [x for x in range(n)]
	wsort = sorted(w)
	luffy = 0
	for x in range(1, len(w)):
		second = w.index(wsort[x])
		prev = w.index(wsort[x - 1])
		while i[second] <= i[prev]:
			luffy += 1
			i[second] += j[second]
	print(luffy)
t = int(input())
for unique in range(t):
	prog_name()


for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	pos = list(range(n))
	wsort = sorted(w)
	if w == wsort:
		print(0)
	else:
		hits = 0
		for i in range(1, n):
			temp = w.index(wsort[i])
			prev = w.index(wsort[i - 1])
			if pos[temp] > pos[prev]:
				continue
			else:
				while pos[temp] <= pos[prev]:
					hits += 1
					pos[temp] += l[temp]
		print(hits)


import math
for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	dict = {}
	ans = 0
	for i in range(1, n + 1):
		dict[i] = w.index(i)
	for i in range(2, n + 1):
		x = dict[i]
		y = dict[i - 1]
		z = 0
		if x <= y:
			z = math.ceil((y - x + 1) / l[x])
		ans += z
		dict[i] += z * l[x]
	print(ans)


import math
t = int(input())
while t:
	n = int(input())
	a = list((int(i) for i in input().split(' ')))
	p = list((int(i) for i in input().split(' ')))
	arr = [0] * 100
	arr[a.index(1)] = 1
	count = 0
	for i in range(2, n + 1):
		if arr.index(i - 1) < a.index(i):
			arr[a.index(i)] = i
		elif int((arr.index(i - 1) + 1 - a.index(i)) / p[a.index(i)]) <= 0:
			arr[a.index(i) + p[a.index(i)]] = i
			count += 1
		else:
			arr[a.index(i) + math.ceil((arr.index(i - 1) + 1 - a.index(i)) / p[a.index(i)]) * p[a.index(i)]] = i
			count += math.ceil((arr.index(i - 1) + 1 - a.index(i)) / p[a.index(i)])
	print(count)
	t -= 1


t = int(input())
ans = []
while t:
	slist = [0] * 30
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	m = min(w)
	for i in range(n):
		slist[i] = w[i]
	kick = 0
	lastpos = w.index(m)
	for i in range(n - 1):
		mv = min((j for j in w if j > m))
		if w.index(mv) > lastpos:
			m = mv
			lastpos = w.index(mv)
			continue
		else:
			nextpos = w.index(mv)
			inc = l[w.index(mv)]
			while True:
				kick += 1
				nextpos += inc
				if nextpos > lastpos:
					slist[nextpos] = mv
					lastpos = nextpos
					break
		m = mv
	ans.append(kick)
	t -= 1
for i in ans:
	print(i)


from math import ceil
T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	W = [int(i) for i in input().split()]
	L = [int(i) for i in input().split()]
	P = {}
	for i in range(N):
		P[i] = i
	visited = [False for i in range(N)]
	count = 0
	for i in range(N):
		mn = float('inf')
		mi = None
		for j in range(N):
			if W[j] < mn and visited[j] == False:
				mn = W[j]
				mi = j
		visited[mi] = True
		for j in range(N):
			if P[j] <= P[mi] and W[j] > W[mi]:
				x = (P[mi] - P[j]) / L[j]
				if x == int(x):
					count += x + 1
					P[j] += L[j] * (x + 1)
				else:
					count += ceil(x)
					P[j] += L[j] * ceil(x)
	ans.append(int(count))
for i in ans:
	print(i)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	A = []
	for __ in range(n):
		A.append([w[__], l[__]])
	B = sorted(A)
	pos = 0
	for i in range(n):
		if A[i][0] == B[0][0] and A[i][1] == B[0][1]:
			pos = i
	ans = 0
	for i in range(1, n):
		newpos = i
		for j in range(n):
			if A[j][0] == B[i][0] and A[j][1] == B[i][1]:
				newpos = j
		req = pos + 1
		noofjumps = 0
		if req - newpos > 0:
			noofjumps = math.ceil((req - newpos) / B[i][1])
		ans += noofjumps
		pos = newpos + B[i][1] * noofjumps
	print(ans)


a = int(input())
for i in range(a):
	n = int(input())
	li = list(map(int, input().split()))
	li2 = list(map(int, input().split()))
	res = 0
	if n == 2:
		if li[0] < li[1]:
			res = 0
		elif li2[0] == 1:
			res = 2
		else:
			res = 1
	dict2 = {}
	dict1 = {}
	k = 1
	if n == 3:
		for j in li:
			dict2[j] = k
			dict1[j] = k
			k = k + 1
		while 1:
			if dict2[1] >= dict2[2]:
				dict2[2] = dict2[2] + li2[dict1[2] - 1]
				res = res + 1
			else:
				break
		while 1:
			if dict2[2] >= dict2[3]:
				dict2[3] = dict2[3] + li2[dict1[3] - 1]
				res = res + 1
			else:
				break
	k = 1
	if n == 4:
		for j in li:
			dict2[j] = k
			dict1[j] = k
			k = k + 1
		while 1:
			if dict2[1] >= dict2[2]:
				dict2[2] = dict2[2] + li2[dict1[2] - 1]
				res = res + 1
			else:
				break
		while 1:
			if dict2[2] >= dict2[3]:
				dict2[3] = dict2[3] + li2[dict1[3] - 1]
				res = res + 1
			else:
				break
		while 1:
			if dict2[3] >= dict2[4]:
				dict2[4] = dict2[4] + li2[dict1[4] - 1]
				res = res + 1
			else:
				break
	print(res)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = list(map(int, input().split()))
	t = sorted(l)
	c = l.index(1)
	p = 0
	for i in range(1, n):
		k = l.index(t[i])
		if k > c:
			c = k
			continue
		j = math.ceil((abs(c - k) + 1) / m[k])
		if j == 0:
			j += 1
		p += j
		c = k + j * m[k]
	print(p)


def frogSort(w, l):
	hits = 0
	pos = {}
	i = 0
	while i < len(w):
		tracker = list()
		tracker.append(i)
		tracker.append(l[i])
		pos[w[i]] = tracker
		i += 1
	i = 1
	while i < len(w):
		while pos[i][0] >= pos[i + 1][0]:
			pos[i + 1][0] += pos[i + 1][1]
			hits += 1
		i += 1
	return hits
t = int(input())
for i in range(t):
	size = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	print(frogSort(w, l))


import math
try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		w = list(map(int, input().split()))
		l = list(map(int, input().split()))
		pos = [None] * (n + 1)
		jump = [None] * (n + 1)
		for i in range(0, n):
			pos[w[i]] = i
			jump[w[i]] = l[i]
		inc = 0
		if pos[2] <= pos[1]:
			hit = math.ceil(float(pos[1] - pos[2] + 1) / jump[2])
			inc += hit
			pos[2] += hit * jump[2]
		if n > 2:
			if pos[3] <= pos[2]:
				hit = math.ceil(float(pos[2] - pos[3] + 1) / jump[3])
				inc += hit
				pos[3] += hit * jump[3]
		if n > 3:
			if pos[4] <= pos[3]:
				hit = math.ceil(float(pos[3] - pos[4] + 1) / jump[4])
				inc += hit
				pos[4] += hit * jump[4]
		print(inc)
except EOFError as t:
	pass


import math

def frogSort(N, W, L):
	Pos = [-1 for i in range(N + 1)]
	for i in range(1, N + 1):
		Pos[i] = W.index(i)
	totHit = 0
	for i in range(2, N + 1):
		if Pos[i - 1] - Pos[i] >= 0:
			hit = math.ceil((Pos[i - 1] - Pos[i] + 1) / L[W.index(i)])
			totHit += hit
			Pos[i] += L[W.index(i)] * hit
	return totHit
for _ in range(int(input())):
	N = int(input())
	W = list(map(int, input().split()))
	L = list(map(int, input().split()))
	print(frogSort(N, W, L))


import math
for t in range(int(input())):
	n = int(input())
	weight = list(map(int, input().split()))
	length = list(map(int, input().split()))
	ind = {}
	s = 0
	for i in range(1, n + 1):
		ind[i] = weight.index(i)
	for i in range(2, n + 1):
		temp1 = ind[i]
		temp2 = ind[i - 1]
		temp = 0
		if temp1 <= temp2:
			temp = math.ceil((temp2 + 1 - temp1) / length[temp1])
		s += temp
		ind[i] += temp * length[temp1]
	print(s)


for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	d = {}
	le = {}
	for i in range(n):
		d.update({w[i]: i + 1})
		le.update({w[i]: l[i]})
	z = {}
	for i in sorted(d):
		z.update({i: d[i]})
	c = 0
	for i in range(2, n + 1):
		while z[i] <= z[i - 1]:
			z[i] = z[i] + le[i]
			c = c + 1
	print(c)


def find(i, w):
	for j in range(len(w)):
		if w[j] == i:
			return j
	return -1

def frogsort(w, l, n):
	p = [x for x in range(n)]
	ans = 0
	for i in range(2, n + 1):
		f = find(i, w)
		e = find(i - 1, w)
		while p[f] <= p[e]:
			ans += 1
			p[f] += l[f]
	return ans
T = int(input())
for i in range(T):
	n = int(input())
	w = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	print(frogsort(w, l, n))


from math import ceil
t = int(input())
while t:
	n = int(input())
	A = dict()
	B = dict()
	wx = list(map(int, input().split()))
	l = list(map(int, input().split()))
	w = sorted(wx)
	for i in range(len(w)):
		A[wx[i]] = i
	for j in range(len(l)):
		B[wx[j]] = l[j]
	count = 0
	for i in range(len(w) - 1):
		if A[w[i + 1]] <= A[w[i]]:
			jump = int((A[w[i]] - A[w[i + 1]]) / B[w[i + 1]]) + 1
			A[w[i + 1]] += jump * B[w[i + 1]]
			count += jump
	print(count)
	t -= 1


import math
test = int(input())
for _ in range(test):
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	pos = [-1 for _ in range(n + 1)]
	lw = [-1 for _ in range(n + 1)]
	for i in range(n):
		pos[w[i]] = i
	for i in range(n):
		lw[w[i]] = l[i]
	ans = 0
	for i in range(1, n):
		if pos[i + 1] <= pos[i]:
			hits = math.ceil((pos[i] - pos[i + 1] + 1) / lw[i + 1])
			ans += hits
			pos[i + 1] += hits * lw[i + 1]
	print(ans)


import math, sys
from collections import defaultdict, Counter, deque
from bisect import bisect_left, bisect_right
INF = float('inf')
MOD = int(1000000000.0) + 7
MAX = int(1000000.0) + 1

def solve():
	n = int(input())
	arr = array()
	jumps = array()
	index = {}
	for i in range(n):
		index[arr[i]] = i
	ans = sorted(arr)
	prev = -1
	res = 0
	for i in range(n):
		j = index[ans[i]]
		jump = jumps[j]
		if prev != -1 or j <= prev:
			while j <= prev:
				j += jump
				res += 1
		prev = j
	print(res)

def main():
	t = 1
	t = int(input())
	for _ in range(t):
		solve()

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def input():
	return sys.stdin.readline().rstrip('\n').strip()

def print(*args, sep=' ', end='\n'):
	first = True
	for arg in args:
		if not first:
			sys.stdout.write(sep)
		sys.stdout.write(str(arg))
		first = False
	sys.stdout.write(end)
primes = [1 for i in range(MAX)]

def sieve():
	global primes
	primes[0] = primes[1] = 0
	i = 2
	while i <= MAX ** 0.5:
		j = i * i
		while primes[i] and j < MAX:
			if j % i == 0:
				primes[j] = 0
			j += i
		i += 1

def vars():
	return map(int, input().split())

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


import math
for _ in range(int(input())):
	N = int(input())
	W = [int(x) for x in input().split()]
	L = [int(x) for x in input().split()]
	pos = [0] * (N + 1)
	L_inv = [0] * (N + 1)
	for i in range(N):
		pos[W[i]] = i
		L_inv[W[i]] = L[i]
	(ans, hits) = (0, 0)
	if pos[2] <= pos[1]:
		hits = math.ceil((pos[1] - pos[2] + 1) / L_inv[2])
		ans += hits
		pos[2] += hits * L_inv[2]
	if N > 2:
		if pos[3] <= pos[2]:
			hits = math.ceil((pos[2] - pos[3] + 1) / L_inv[3])
			ans += hits
			pos[3] += hits * L_inv[3]
	if N > 3:
		if pos[4] <= pos[3]:
			hits = math.ceil((pos[3] - pos[4] + 1) / L_inv[4])
			ans += hits
			pos[4] += hits * L_inv[4]
	print(ans)


from math import ceil
for _ in range(int(input())):
	n = int(input())
	weights = list(map(int, input().split()))
	leaps = list(map(int, input().split()))
	frog = [[weights[i], i, leaps[i]] for i in range(n)]
	frog.sort()
	ans = 0
	for i in range(n):
		for j in range(i + 1, n):
			if frog[j][0] > frog[i][0] and frog[j][1] <= frog[i][1]:
				dist = frog[i][1] + 1 - frog[j][1]
				jmps_req = ceil(dist / frog[j][2])
				ans += jmps_req
				frog[j][1] += jmps_req * frog[j][2]
	print(ans)


for test_case in range(int(input())):
	size = int(input())
	weight = [int(x) for x in input().split()]
	step = [int(x) for x in input().split()]
	hit = 0
	weightPos = {}
	for i in range(size):
		weightPos[weight[i]] = i
	weight.sort()
	lastPos = weightPos[weight[0]]
	for i in range(1, size):
		currPos = weightPos[weight[i]]
		index = weightPos[weight[i]]
		while lastPos >= currPos:
			currPos += step[index]
			hit += 1
		lastPos = currPos
	print(hit)


try:
	t = int(input())
	for i in range(t):
		n = int(input())
		warr = list(map(int, input().split()))
		larr = list(map(int, input().split()))
		positions = [[0, 0] for i in range(n)]
		for i in warr:
			positions[i - 1][0] = warr.index(i)
			positions[i - 1][1] = larr[warr.index(i)]
		output = 0
		for i in range(1, n):
			if positions[i][0] <= positions[i - 1][0]:
				pos_diff = positions[i - 1][0] - positions[i][0]
				inc = positions[i][1]
				jumps = pos_diff // inc + 1
				output += jumps
				positions[i][0] += jumps * inc
		print(output)
except EOFError:
	pass


t = int(input())
while t > 0:
	t -= 1
	N = int(input())
	wi = list(map(int, input().split()))
	li = list(map(int, input().split()))
	si = [0] * N
	pi = [0] * N
	for i in range(0, N):
		si[i] = li[wi.index(i + 1)]
		pi[wi[i] - 1] = i
	lock = 0
	count = 0
	while lock == 0:
		flag = 0
		for i in range(0, N - 1):
			if pi[i] >= pi[i + 1]:
				pi[i + 1] += si[i + 1]
				flag = 1
				count += 1
		if flag == 0:
			lock = 1
	print(count)


for _ in range(int(input())):
	N = int(input())
	pos = {}
	W = [int(x) for x in input().split()]
	L = [int(x) for x in input().split()]
	for i in range(N):
		pos[W[i]] = [i + 1, L[i]]
	cnt = 0
	for w in range(2, N + 1):
		while pos[w][0] <= pos[w - 1][0]:
			pos[w][0] += pos[w][1]
			cnt += 1
	print(cnt)


import math
for test_case in range(int(input())):
	n = int(input())
	w = [int(x) for x in input().split()]
	l = [int(y) for y in input().split()]
	wIndex = {}
	wL = {}
	output = 0
	for x in w:
		wIndex[w[x - 1]] = x
		wL[w[x - 1]] = l[x - 1]
	for i in range(2, n + 1):
		if wIndex[i - 1] >= wIndex[i]:
			output += math.ceil((wIndex[i - 1] - wIndex[i] + 1) / wL[i])
			wIndex[i] += math.ceil((wIndex[i - 1] - wIndex[i] + 1) / wL[i]) * wL[i]
	print(output)


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))[:n]
	b = list(map(int, input().split()))[:n]
	c = []
	d = []
	for i in range(n):
		c.append(0)
		d.append(0)
	step = 0
	steps = 0
	for i in range(n):
		c[a[i] - 1] = i
		d[a[i] - 1] = b[i]
	for i in range(n - 1):
		if c[i] >= c[i + 1]:
			step = int((c[i] - c[i + 1]) / d[i + 1]) + 1
			c[i + 1] += d[i + 1] * step
			steps += step
	print(steps)
	t = t - 1


import sys
import math
import itertools
import functools
import collections
import operator
import fileinput
import copy
from collections import *
ORDA = 97

def ii():
	return int(input())

def mi():
	return map(int, input().split())

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

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def revn(n):
	return str(n)[::-1]

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=2):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def convn(number, base):
	new_number = 0
	while number > 0:
		new_number += number % base
		number //= base
	return new_number

def cdiv(n, k):
	return n // k + (n % k != 0)

def ispal(s):
	for i in range(len(s) // 2 + 1):
		if s[i] != s[-i - 1]:
			return False
	return True

def function(arr, size, dp):
	if size == 1 or size == 0:
		return 1
	key = ''.join(map(str, arr[:size]))
	if dp[key]:
		return dp[key]
	output = function(arr, size - 1, dp)
	key = ''.join(map(str, arr[:size - 1]))
	dp[key] = output
	if arr[size - 2] * 10 + arr[size - 1] <= 26:
		output += function(arr, size - 2, dp)
		key = ''.join(map(str, arr[:size - 2]))
		dp[key] = output
	return output

def main():
	for _ in range(ii()):
		n = ii()
		fweight = li()
		l = li()
		d = {}
		for i in range(n):
			d[fweight[i]] = l[i]
		prev_frog = fweight.index(1)
		hits = 0
		for f in range(2, n + 1, 1):
			cur_frog = fweight.index(f)
			if cur_frog > prev_frog:
				prev_frog = cur_frog
				continue
			else:
				while cur_frog <= prev_frog:
					hits += 1
					cur_frog += d[f]
				prev_frog = cur_frog
		print(hits)
main()


t = int(input())
for i in range(t):
	N = int(input())
	a = input()
	W = a.split(' ')
	b = input()
	L = b.split(' ')
	n = 0
	tap = 0
	for i in range(len(W)):
		W[i] = int(W[i])
	link = {}
	for i in range(1, N + 1):
		link[i] = W.index(i)
	for i in range(2, N + 1):
		temp1 = link.get(i)
		temp2 = link.get(i - 1)
		if temp2 >= temp1:
			n = (temp2 - temp1) // int(L[W.index(i)]) + 1
			tap += n
			link[i] += n * int(L[W.index(i)])
	print(tap)


n = int(input())
for i in range(0, n):
	nf = int(input())
	f = list(map(int, input().split()))
	fw = list(map(int, input().split()))
	p = {}
	w = {}
	c = 0
	s = sorted(f)
	for j in range(0, len(f)):
		p[f[j]] = j
		w[f[j]] = fw[j]
	while p[s[1]] <= p[s[0]]:
		p[s[1]] = p[s[1]] + w[s[1]]
		c = c + 1
	if nf >= 3:
		while p[s[2]] <= p[s[1]]:
			p[s[2]] = p[s[2]] + w[s[2]]
			c = c + 1
	if nf == 4:
		while p[s[3]] <= p[s[2]]:
			p[s[3]] = p[s[3]] + w[s[3]]
			c = c + 1
	print(c)


import math
t = int(input())
for testcases in range(t):
	n = int(input())
	W = [int(x) for x in input().split(' ')]
	P = [-1] * n
	for w in range(n):
		P[W[w] - 1] = w
	L = [int(x) for x in input().split(' ')]
	max_index = n
	curr_index = 0
	count = 0
	for p in range(1, n):
		if P[p] <= P[p - 1]:
			ce = math.ceil((P[p - 1] - P[p] + 1) / L[P[p]])
			count += ce
			P[p] += L[P[p]] * ce
	print(count)


from collections import Counter, defaultdict
from math import ceil
for i in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	a = sorted(w)
	j = 1
	ans = 0
	indp = w.index(a[j - 1])
	while j < n:
		ind = w.index(a[j])
		cind = ind
		while ind <= indp:
			ind += l[cind]
			ans += 1
		indp = ind
		j += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	temp = list(map(int, input().split()))
	k = 0
	curIndex = {}
	cap = {}
	for j in arr:
		curIndex[j] = k
		cap[j] = temp[k]
		k = k + 1
	cnt = 0
	for r in range(2, n + 1):
		x = 0
		a = curIndex[r]
		b = curIndex[r - 1]
		if a <= b:
			diff = b - a
			x = int(diff / cap[r]) + 1
			curIndex[r] = curIndex[r] + x * cap[r]
		cnt = cnt + x
	print(cnt)


for _ in range(int(input())):
	N = int(input())
	W = list(map(int, input().split()))
	L = list(map(int, input().split()))
	pos = {}
	for i in range(N):
		pos[W[i]] = i + 1
	init_pos = pos
	hits = 0
	for i in range(2, N + 1):
		jumps = L[init_pos[i] - 1]
		if pos[i] <= pos[i - 1]:
			separation = pos[i - 1] - pos[i]
			if separation < jumps:
				hits += 1
				pos[i] += jumps
			else:
				hits = hits + separation // jumps + 1
				pos[i] += jumps * (separation // jumps + 1)
	print(hits)


import math

def sol():
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	sorted_arr = True
	pos = dict()
	for i in range(n):
		pos[w[i]] = i
	step = dict()
	for i in range(n):
		step[w[i]] = l[i]
	for i in range(n):
		if pos[i + 1] != i:
			sorted_arr = False
			break
	if sorted_arr:
		return 0
	hit = 0
	for i in range(2, n + 1):
		if pos[i] <= pos[i - 1]:
			temp = math.ceil((pos[i - 1] - pos[i] + 1) / step[i])
			hit += temp
			pos[i] += temp * step[i]
	return hit
tests = int(input())
for _ in range(tests):
	print(sol())


import math

def hitt(p1, p2, l):
	i = math.ceil((p1 - p2 + 1) / l)
	return i
for _ in range(int(input())):
	n = int(input())
	n_w = list(map(int, input().split()[:n]))
	n_l = list(map(int, input().split()[:n]))
	hit = 0
	j = 0
	p1 = n_w.index(1)
	p2 = n_w.index(2)
	if n >= 1 and p1 >= p2:
		j = hitt(p1, p2, n_l[p2])
		hit += j
	p1 = p2 + j * n_l[p2]
	if n >= 2:
		for i in range(1, n - 1):
			j = 0
			p2 = n_w.index(i + 2)
			l = n_l[p2]
			if p1 >= p2:
				j = hitt(p1, p2, l)
				hit += j
			p1 = p2 + j * n_l[p2]
	print(hit)


t = int(input())
for i in range(t):
	d = int(input())
	c = input().rstrip().split(' ')
	f = input().rstrip().split(' ')
	dictt = dict()
	for j in c:
		dictt.setdefault(int(j), c.index(j))
	c.sort()
	hit = 0
	for o in range(len(c) - 1):
		l = int(c[o])
		k = int(c[o + 1])
		index = dictt.get(k)
		while dictt.get(k) <= dictt.get(l):
			dictt[k] = dictt.get(k) + int(f[index])
			hit = hit + 1
	print(hit)


tcase = int(input())
for i in range(tcase):
	n = int(input())
	wi = input().split()
	wi = list(map(int, wi))
	li = input().split()
	li = list(map(int, li))
	pos = range(1, n + 1)
	lipos = list()
	for j in range(n):
		temp = (li[j], pos[j])
		lipos.append(temp)
	res = dict(zip(wi, lipos))
	wi.sort()
	templt1 = []
	templt2 = []
	for j in range(n):
		templt1.append(res[wi[j]][0])
		templt2.append(res[wi[j]][1])
	li = templt1
	pos = templt2
	count = 0
	for j in range(n - 1):
		if pos[j] >= pos[j + 1]:
			temp2 = (pos[j] - pos[j + 1]) // li[j + 1] + 1
			pos[j + 1] = pos[j + 1] + temp2 * li[j + 1]
			count = count + temp2
	print(count)


for test in range(int(input())):
	n = int(input())
	weights = list(map(int, input().split()))
	leaps = list(map(int, input().split()))
	position = {weights[ind]: ind + 1 for ind in range(n)}
	link = dict(zip(weights, leaps))
	hits = 0
	for i in range(1, n):
		if position[i] >= position[i + 1]:
			ihit = 1 + (position[i] - position[i + 1]) // link[i + 1]
			hits += ihit
			position[i + 1] += ihit * link[i + 1]
	print(hits)


t = int(input())
for _ in range(t):
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	frogs = []
	for i in range(n):
		frogs.append([w[i], l[i], i])
	result = 0
	for i in range(100):
		for j in range(n - 1):
			if frogs[j][0] > frogs[j + 1][0]:
				frogs[j][2] += frogs[j][1]
				result += 1
			frogs.sort(key=lambda x: x[2])
	for i in range(1, n):
		while frogs[i][2] <= frogs[i - 1][2]:
			frogs[i][2] += frogs[i][1]
			result += 1
	print(result)


from math import ceil
for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	if n >= 2:
		ans = 0
		one = w.index(1)
		two = w.index(2)
		i = 0
		if one >= two:
			i = ceil((one - two + 1) / l[two])
			ans += i
		if n >= 3:
			two += i * l[two]
			three = w.index(3)
			j = 0
			if two >= three:
				j = ceil((two - three + 1) / l[three])
				ans += j
			k = 0
			if n == 4:
				three += j * l[three]
				four = w.index(4)
				if three >= four:
					k = ceil((three - four + 1) / l[four])
					ans += k
	print(ans)


T = int(input())
for _ in range(T):
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	if n == 1:
		print(0)
	elif n == 2:
		(x1, x2) = (0, 0)
		(l1, l2) = (0, 0)
		for i in range(2):
			if w[i] == 1:
				x1 = i
				l1 = l[i]
			elif w[i] == 2:
				x2 = i
				l2 = l[i]
		j = 0
		if x2 <= x1:
			while x2 <= x1:
				j += 1
				x2 += l2
		print(j)
	elif n == 3:
		(x1, x2, x3) = (0, 0, 0)
		(l1, l2, l3) = (0, 0, 0)
		for i in range(3):
			if w[i] == 1:
				x1 = i
				l1 = l[i]
			elif w[i] == 2:
				x2 = i
				l2 = l[i]
			elif w[i] == 3:
				x3 = i
				l3 = l[i]
		j = 0
		if x2 <= x1:
			while x2 <= x1:
				j += 1
				x2 += l2
		if x3 <= x2:
			while x3 <= x2:
				j += 1
				x3 += l3
		print(j)
	else:
		(x1, x2, x3, x4) = (0, 0, 0, 0)
		(l1, l2, l3, l4) = (0, 0, 0, 0)
		for i in range(4):
			if w[i] == 1:
				x1 = i
				l1 = l[i]
			elif w[i] == 2:
				x2 = i
				l2 = l[i]
			elif w[i] == 3:
				x3 = i
				l3 = l[i]
			else:
				x4 = i
				l4 = l[i]
		j = 0
		if x2 <= x1:
			while x2 <= x1:
				j += 1
				x2 += l2
		if x3 <= x2:
			while x3 <= x2:
				j += 1
				x3 += l3
		if x4 <= x3:
			while x4 <= x3:
				j += 1
				x4 += l4
		print(j)


for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	l = list(map(int, input().split()))
	pos = [i for i in range(n)]
	sw = []
	for i in w:
		sw.append(i)
	sw.sort()
	ans = 0
	for i in range(1, n):
		ind2 = w.index(sw[i])
		ind1 = pos[w.index(sw[i - 1])]
		idx = ind2
		while idx <= ind1:
			idx += l[ind2]
			pos[ind2] = idx
			ans += 1
	print(ans)