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

You are given an undirected graph with N nodes (numbered 1 through N). For each valid i, the i-th node has a weight W_{i}. Also, for each pair of nodes i and j, there is an edge connecting these nodes if j - i \neq W_{j} - W_{i}.

Find the number of connected components in this graph.

------ Input Format ------ 

- 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}.

------ Output Format ------ 

For each test case, print a single line containing one integer --- the number of connected components in the graph.

------ Constraints ------ 

$1 ≤T ≤10^{4}$
$1 ≤N ≤10^{5}$
$|W_{i}| ≤10^{9}$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$

------ subtasks ------ 

Subtask #1 (30 points):
$N ≤10^{3}$
the sum of $N$ over all test cases does not exceed $2 \cdot 10^{3}$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
2
2
1 2
2
2 1

----- Sample Output 1 ------ 
2
1
----- explanation 1 ------ 
Example case 1: For $i=1$ and $j=2$, we have $2-1 = 2-1$, therefore there are no edges in the graph and there are two connected components.

Example case 2: For $i=1$ and $j=2$, we have $2-1 \neq 1-2$, therefore there is an edge between $1$ and $2$, the graph is connected, so there is only one connected component.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	W = list(map(int, input().split()))
	X = [W[i] - (i + 1) for i in range(n)]
	if all([X[i] == X[0] for i in range(n)]):
		print(n)
	else:
		print(1)


t = int(input())
while t != 0:
	n = int(input())
	s = set()
	l = list(map(int, input().split()))
	for i in range(n):
		s.add(l[i] - i)
	if len(s) == 1:
		print(n)
	else:
		print(1)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	b = []
	for (i, v) in enumerate(l):
		b.append((v, i))
	l = b
	l.sort()
	f = l[0][0]
	for i in range(n):
		l[i] = (l[i][0] - f, l[i][1])
	l.sort(key=lambda a: a[1])
	l = [i[0] for i in l]
	for (i, v) in enumerate(l):
		if i != v:
			c = 1
			break
	if c:
		print(1)
	else:
		print(n)


(i, j) = (input, int)
for t in [0] * j(i()):
	n = j(i())
	(*w,) = map(j, i().split())
	for k in range(n):
		w[k] -= k
	print([1, n][len(set(w)) < 2])


for tea in range(int(input())):
	n = int(input())
	waw = [int(x) for x in input().split()]
	for i in range(n):
		waw[i] -= i
	if len(set(waw)) == 1:
		print(n)
	else:
		print(1)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	d = defaultdict(lambda : 0)
	for i in range(n):
		d[w[i] - i] += 1
	if len(d) == 1:
		print(n)
	else:
		print(1)


for z in range(int(input())):
	n = int(input())
	w = [int(x) for x in input().split()]
	v = set()
	b = True
	for i in range(1, n + 1):
		if i - w[i - 1] in v:
			b = False
		v.add(i - w[i - 1])
	if b:
		print(1)
	else:
		print(n)


t = int(input())
while t > 0:
	n = int(input())
	c = 0
	res = list(map(int, input().strip().split()))[:n]
	for i in range(1, n):
		if i + 1 - i == res[i] - res[i - 1]:
			c = n
		else:
			c = n - i
	print(c)
	t = t - 1


import collections
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	s = set()
	for i in range(len(arr)):
		s.add(arr[i] - i)
	if len(s) == 1:
		print(n)
	else:
		print(1)


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	s = set()
	for i in range(a):
		s.add(l[i] - i)
	if len(s) == 1:
		print(a)
	else:
		print(1)


from collections import Counter, defaultdict

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

def main():
	count = 0
	temp = [lst[i] - (i + 1) for i in range(n)]
	dct = Counter(temp)
	for ele in dct:
		count = max(dct[ele], count)
	print(count)
t = int(input())
for _ in range(t):
	n = int(input())
	lst = integer_list()
	main()


import math
import sys
from collections import Counter, defaultdict
mod = 1000000007

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

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())

def main():
	node = set()
	graph = defaultdict(list)
	count = 0
	temp = [lst[i] - (i + 1) for i in range(n)]
	dct = Counter(temp)
	for ele in dct:
		count = max(dct[ele], count)
	print(count)
t = int(input())
for _ in range(t):
	n = int(input())
	lst = integer_list()
	visited = set()
	main()


t = int(input())
for i in range(t):
	n = int(input())
	w = list(map(int, input().split()))
	for i in range(n):
		w[i] = w[i] - i
	print(n - len(set(w)) + 1)


from heapq import heapify, heappush, heappop
from cmath import pi
from distutils import extension
from pickle import FALSE
import sys
from math import gcd, sqrt, log10, log2, floor, ceil
from collections import deque, defaultdict
from tkinter.tix import Tree
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

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

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
for _ in range(ii()):
	n = ii()
	arr = il()
	for l in range(n):
		arr[l] -= l
	d = {}
	for l in arr:
		if l in d:
			d[l] = d[l] + 1
		else:
			d[l] = 1
	print(d[arr[0]])


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	W = set(A)
	count = 0
	if len(W) == 1:
		print(N)
	else:
		for i in range(N - 1):
			j = i + 1
			if A[j] - A[i] != j - i:
				count = 1
	print(1 if count > 0 else N)


for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	ans = set()
	for i in range(n):
		ans.add(w[i] - i)
	if len(ans) == 1:
		print(n)
	else:
		print(1)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	for i in range(len(arr) - 1):
		j = i + 1
		if arr[j] - arr[i] != j - i:
			count += 1
	if count > 0:
		print(1)
	else:
		print(n)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = [l[x] - x + 1 for x in range(n)]
	print(n if len(set(s)) == 1 else 1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l = [l[i] - i + 1 for i in range(n)]
	if len(set(l)) == 1:
		print(n)
	else:
		print(1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	a = [a[i] - i for i in range(n)]
	res = 0
	for i in range(1, n):
		if a[i] != a[0]:
			res = 1
	if res == 1:
		print(1)
	else:
		print(n)


try:
	for t in range(int(input())):
		N = int(input())
		W = list(map(int, input().split()))
		A = []
		for i in range(N):
			A.append(W[i] - i)
		flag = 0
		for i in range(N):
			if A[i] != A[0]:
				flag = 1
				break
		if flag == 1:
			print(1)
		else:
			print(N)
except:
	pass


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	diff = []
	for i in range(n):
		diff.append(arr[i] - i)
	c = Counter(diff)
	if len(c) > 1:
		ans = 1
	else:
		ans = c[arr[0]]
	print(ans)


try:
	for T in range(int(input())):
		N = int(input())
		A = list(map(int, input().split()))
		const = []
		for i in range(N):
			const.append(A[i] - i + 1)
		if const.count(const[0]) == N:
			print(N)
		else:
			print(1)
except:
	pass


for _ in range(int(input())):
	n = int(input())
	w_s = list(map(int, input().split()))
	index = 0
	count = 0
	for i in range(len(w_s) - 1):
		if i + 1 - i != w_s[i + 1] - w_s[i]:
			count = 1
			break
	if count > 0:
		print(1)
	else:
		print(n)


t = int(input())
while t:
	s = set()
	n = int(input())
	w = list(map(int, input().split()))
	for j in range(n):
		s.add(w[j] - j)
	if len(s) == 1:
		print(n)
	else:
		print('1')
	t -= 1


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[l[i] - i] = 1
	if len(d) == 1:
		print(n)
	else:
		print(1)


def solve():
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	for i in range(n):
		arr[i] = arr[i] - i
	if len(set(arr)) == 1:
		print(n)
	else:
		print(1)
t = int(input())
while t:
	solve()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	graph = []
	flag = 0
	for i in range(n):
		graph.append(L[i] - i)
	for i in range(1, n):
		if graph[i] != graph[i - 1]:
			flag = 1
			break
	if flag == 1:
		print(1)
	else:
		print(len(graph))


for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [a[i] - i for i in range(n)]
	if b.count(b[0]) == len(b):
		print(n)
	else:
		print(1)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	m = dict()
	for i in range(n):
		arr[i] = arr[i] - (i + 1)
		if arr[i] not in m:
			m[arr[i]] = 0
		m[arr[i]] += 1
	if len(m) == 1:
		print(n)
	else:
		print(1)


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	set1 = set(arr)
	if len(set1) == 1:
		print(n)
	else:
		count = 0
		for i in range(len(arr) - 1):
			j = i + 1
			if arr[j] - arr[i] != j - i:
				count += 1
	if count > 0:
		print('1')
	else:
		print(n)
	t -= 1


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	s = set()
	for i in range(len(A)):
		s.add(A[i] - i)
	if len(s) == 1:
		print(N)
	else:
		print(1)


for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	a = []
	for i in range(n):
		a.append(w[i] - i)
	if len(set(a)) == 1:
		print(n)
	else:
		print(1)


t = int(input())
while t > 0:
	n = int(input())
	w = list(map(int, input().strip().split()))
	temp = set()
	for i in range(len(w)):
		temp.add(w[i] - i)
	if len(temp) == 1:
		print(n)
	else:
		print('1')
	t -= 1


t = int(input())
for xx in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	res = False
	for i in range(1, n):
		if arr[i] - arr[i - 1] != 1:
			res = True
			break
	if res:
		print(1)
	else:
		print(n)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = n
	for i in range(n):
		if l[0] + i != l[i]:
			c -= 1
	print(c)


for i in range(int(input())):
	N = int(input())
	weights = list(map(int, input().split()))
	arr = []
	for i in range(len(weights)):
		arr.append(weights[i] - i)
	if len(set(arr)) == 1:
		print(N)
	else:
		print(1)


T = int(input())
for tc in range(T):
	n = int(input())
	counter = 1
	weights = [int(i) for i in input().split()]
	for i in range(n - 1):
		if weights[i + 1] - weights[i] == 1:
			counter += 1
	print(counter)


for _ in range(0, int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	count = 1
	ans = 0
	for i in range(0, n - 1):
		if l[i] + 1 == l[i + 1]:
			count += 1
		else:
			count = 1
			ans = ans + count
	if count > 1:
		ans = ans + count
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	d = {}
	for i in range(n):
		l[i] = l[i] - i
		d[l[i]] = True
	if len(d) == 1:
		print(n)
	else:
		print('1')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 1
	for i in range(1, n):
		if a[i] - a[i - 1] == 1:
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	N = int(input())
	c = 1
	A = list(map(int, input().split()))
	for i in range(N):
		A[i] -= c
		c += 1
	S = set(A)
	if len(S) == 1:
		print(N)
	else:
		print(1)


t = int(input())
for _ in range(t):
	n = int(input())
	wt = list(map(int, input().split()))
	dic = {}
	for i in range(n):
		x = wt[i] - i - 1
		if x in dic:
			dic[x].append(i)
		else:
			dic[x] = [i]
	if len(dic) > 1:
		print(1)
	else:
		print(len(dic[list(dic.keys())[0]]))


t = int(input())
for tt in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(n):
		arr[i] = arr[i] - i
	arr = set(arr)
	if len(arr) == 1:
		print(n)
	else:
		print(1)


test = int(input())
for i in range(0, test):
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(0, len(arr)):
		arr[i] = arr[i] - i
	same = 0
	for i in range(0, len(arr) - 1):
		if arr[i] != arr[i + 1]:
			same = 1
	if same:
		print(1)
	else:
		print(n)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(1)
	else:
		for i in range(1, n):
			if l[i] - l[i - 1] != 1:
				print(1)
				break
		else:
			print(n)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(len(l)):
		l[i] = l[i] - (i + 1)
	l = set(l)
	print(n + 1 - len(l))


def solve():
	t = int(input())
	for j in range(t):
		n = int(input())
		w = list(map(int, input().split()))
		par = set()
		for i in range(n):
			par.add(w[i] - i)
		l = len(par)
		if l == 1:
			print(n)
		else:
			print(1)
solve()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	num = []
	for i in range(n):
		num.append(l[i] - i - 1)
	if len(set(num)) == 1:
		print(n)
	else:
		print(1)


for _ in range(int(input())):
	n = int(input())
	nodes = list(map(int, input().split()))
	flag = 1
	for i in range(1, n):
		if nodes[0] != nodes[i] - i:
			flag = 0
			break
	print(1 if flag == 0 else n)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(n):
		l[i] -= i
	ans = 1
	if max(l) == min(l):
		ans = n
	print(ans)


for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	cnt = 0
	for i in range(n - 1):
		if w[i + 1] - w[i] == 1:
			cnt += 1
	if cnt == n - 1:
		print(n)
	else:
		print(1)


t = int(input())
for r in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = a[0] - 1
	for rr in range(1, n):
		if a[rr] - rr - 1 == b:
			continue
		else:
			print(1)
			break
	else:
		print(n)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	k = 0
	for i in range(n - 1):
		if l[i + 1] - l[i] != 1:
			k += 1
	if k > 0:
		print(1)
	else:
		print(n)


t_tests = int(input())
for t in range(t_tests):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	lt = 1
	for i in range(0, n - 1):
		if 1 == arr[i + 1] - arr[i]:
			lt += 1
	print(lt)


for _ in range(int(input())):
	n = int(input())
	weightList = list(map(int, input().split()))
	counter = 0
	for i in range(n - 1):
		j = i + 1
		if not j - i == weightList[j] - weightList[i]:
			counter += 1
	if counter > 0:
		print(1)
	else:
		print(n)


num = int(input())
for i in range(num):
	num1 = int(input())
	w = list(map(int, input().split()))
	n = [0] * (num1 + 1)
	for i in range(1, len(w) + 1):
		n[i] = i
	d = []
	for j in range(len(w)):
		d.append(w[j] - n[j + 1])
	f = 0
	for k in range(num1 - 1):
		if d[k] != d[k + 1]:
			f = 1
			break
	if f == 0:
		print(len(w))
	else:
		print(1)