There is an array A with N elements. Each element of A has a fixed *polarity*: either north or south. 

Chef is allowed to perform some (possibly zero) operations on the array A. In one operation, Chef can:

Pick some subarray of array A, such that, the first and last elements of the subarray have different polarities, and, rearrange the elements in this subarray any way he wants. 

Note that the polarity of each element remains unchanged after an operation.

Find the minimum number of operations required to sort the array in non-decreasing order, or state that it is impossible.

A subarray of A is obtained by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

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

- The first line contains an integer T, denoting the number of test cases. The T test cases then follow.
- The first line of each test case contains a single integer N.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.
- The third line of each test case contains a string of length N, the ith character of which is either \texttt{N} or \texttt{S}, representing that the ith element of A has north or south polarity, respectively.

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

For each test case, if it impossible to sort the array, output -1. Otherwise, output a single integer: the minimum number of operations required to sort the array.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ across all test cases doesn't exceed $2 \cdot 10^{5}$.

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

Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
6
5
1 3 2 3 7
NNSNS
2
2 1
SS
3
1 8 12
SNS
3
3 2 1
NSN
5
1 2 3 5 4
NSNSN
5
1 1 2 2 1
SNSNN

----- Sample Output 1 ------ 
1
-1
0
2
1
1

----- explanation 1 ------ 
Let's represent elements with a polarity of north in $\color{red}{\text{red}}$, and elements with a polarity of south in $\color{blue}{\text{blue}}$. The polarity of each element is also labelled above it.

- In the first test case, we can sort the array in a single operation as follows.
- Rearrange the subarray $[A_{1}, A_{2}, A_{3}]$: $[\color{red}{\stackrel{\texttt{N}}{1}}, \color{red}{\stackrel{\texttt{N}}{3}}, \color{blue}{\stackrel{\texttt{S}}{2}}, \color{red}{\stackrel{\texttt{N}}{3}}, \color{blue}{\stackrel{\texttt{S}}{7}}\color{black}{]} \to [\color{red}{\stackrel{\texttt{N}}{1}}, \color{blue}{\stackrel{\texttt{S}}{2}}, \color{red}{\stackrel{\texttt{N}}{3}}, \color{red}{\stackrel{\texttt{N}}{3}}, \color{blue}{\stackrel{\texttt{S}}{7}}\color{black}{]}$.

- In the second test case, the array $[\color{blue}{\stackrel{\texttt{S}}{2}}, \color{blue}{\stackrel{\texttt{S}}{1}}\color{black}{]}$ cannot be sorted, since no operations can be performed.

- In the third test case, the array is already sorted, so the answer is $0$.

- In the fourth test case, we can sort the array in two operations as follows.

- Rearrange the subarray $[A_{2}, A_{3}]$: $[\color{red}{\stackrel{\texttt{N}}{3}}, \color{blue}{\stackrel{\texttt{S}}{2}}, \color{red}{\stackrel{\texttt{N}}{1}}\color{black}{]} \to [\color{red}{\stackrel{\texttt{N}}{3}}, \color{red}{\stackrel{\texttt{N}}{1}}, \color{blue}{\stackrel{\texttt{S}}{2}}\color{black}{]}$.
- Rearrange the subarray $[A_{1}, A_{2}, A_{3}]$: $[\color{red}{\stackrel{\texttt{N}}{3}}, \color{red}{\stackrel{\texttt{N}}{1}}, \color{blue}{\stackrel{\texttt{S}}{2}}\color{black}{]} \to [\color{red}{\stackrel{\texttt{N}}{1}}, \color{blue}{\stackrel{\texttt{S}}{2}}, \color{red}{\stackrel{\texttt{N}}{3}}\color{black}{]}$.

Difficulty: MEDIUM_HARD
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
t = int(input())

def solve():
	N = int(input())
	A = [int(x) for x in input().split(' ')]
	S = input().strip('\n')
	sA = list(sorted(A))
	if sA == A:
		print('0')
		return
	(firsts, firstn, lasts, lastn, firstw, lastw) = [-1] * 6
	for i in range(N):
		if S[i] == 'S':
			if firsts == -1:
				firsts = i
			lasts = i
		else:
			if firstn == -1:
				firstn = i
			lastn = i
		if sA[i] != A[i]:
			if firstw == -1:
				firstw = i
			lastw = i
	if (firsts >= 0 and firstn >= 0) and (firstw >= firsts and lastw <= lastn or (firstw >= firstn and lastw <= lasts)):
		print('1')
	elif firsts >= 0 and firstn >= 0:
		print('2')
	else:
		print('-1')
while t:
	solve()
	t -= 1


def solve(n, a, s):
	b = sorted(a)
	i = 0
	while i < n and a[i] == b[i]:
		i += 1
	if i == n:
		return 0
	if s == 'S' * n or s == 'N' * n:
		return -1
	j = n - 1
	while j >= 0 and a[j] == b[j]:
		j -= 1
	s = s[:i + 1] + s[j:]
	if s == 'S' * (i + 1 + n - j) or s == 'N' * (i + 1 + n - j):
		return 2
	return 1
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	s = input().strip()
	print(solve(n, a, s))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = str(input())
	f = a.copy()
	f.sort()
	if f == a:
		print(0)
	elif p.count('S') == 0 or p.count('N') == 0:
		print(-1)
	elif p[0] != p[-1]:
		print(1)
	elif p[0] == p[-1]:
		sm = True
		em = True
		si = 0
		while p[si] == p[0] and si < n:
			if f[si] != a[si] and p[si] == p[0]:
				sm = False
			si += 1
		ei = n - 1
		while p[ei] == p[0] and ei >= 0:
			if f[ei] != a[ei] and p[ei] == p[0]:
				em = False
			ei -= 1
		if sm == False and em == False:
			print(2)
		else:
			print(1)


for _ in range(int(input())):
	N = input()
	x = list(map(int, input().split()))
	weights = input()
	sx = sorted([(a, b, weights[a]) for (a, b) in enumerate(x)], key=lambda x: x[1])
	first_N = last_N = first_S = last_S = -1
	fS = fN = fX = True
	fu = lu = -1
	m = [float('inf'), -1]
	for i in range(len(x)):
		z = weights[i]
		if fN:
			if z == 'N':
				fN = False
				first_N = i
		if fS:
			if z == 'S':
				fS = False
				first_S = i
		if sx[i][0] != i:
			m[0] = min(m[0], sx[i][0])
			m[1] = max(m[1], sx[i][0])
		if z == 'S':
			last_S = i
		if z == 'N':
			last_N = i
	if m == [float('inf'), -1]:
		print(0)
		continue
	if first_S == -1 or first_N == -1:
		print(-1)
		continue
	if weights[0] != weights[-1]:
		print(1)
		continue
	if first_S <= m[0] and last_N >= m[1] or (first_N <= m[0] and last_S >= m[1]):
		print(1)
		continue
	print(2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	if a == sorted(a):
		print(0)
		continue
	if not s.count('N') or not s.count('S'):
		print(-1)
		continue
	(firstN, firstS, lastN, lastS) = (-1, -1, -1, -1)
	for i in range(n):
		if s[i] == 'N':
			if firstN == -1:
				firstN = i
			lastN = i
		if s[i] == 'S':
			if firstS == -1:
				firstS = i
			lastS = i
	b = sorted(a)
	for i in range(n):
		if (i < firstN or i > lastS) and a[i] != b[i]:
			break
	else:
		print(1)
		continue
	for i in range(n):
		if (i < firstS or i > lastN) and a[i] != b[i]:
			break
	else:
		print(1)
		continue
	print(2)


a = int(input())
for i in range(a):
	N = int(input())
	A = list(map(int, input().split()))
	S = input()
	if sorted(A) == A:
		print(0)
	elif S[0] != S[N - 1]:
		print(1)
	elif S.count(S[0]) == N:
		print(-1)
	elif S[0] == 'N':
		k = S.index('S')
		r = S.rfind('S')
		C = A[:k]
		D = A[r + 1:]
		P = sorted(C)
		Q = sorted(D)
		if C != P and D != Q:
			print(2)
		elif C == P and D != Q:
			if max(C) <= min(A[k:]):
				print(1)
			else:
				print(2)
		elif D == Q and C != P:
			if max(A[:r + 1]) <= min(D):
				print(1)
			else:
				print(2)
		elif max(C) <= min(A[k:]) or max(A[:r + 1]) <= min(D):
			print(1)
		else:
			print(2)
	else:
		k = S.index('N')
		r = S.rfind('N')
		C = A[:k]
		D = A[r + 1:]
		P = sorted(C)
		Q = sorted(D)
		if C != P and D != Q:
			print(2)
		elif C == P and D != Q:
			if max(C) <= min(A[k:]):
				print(1)
			else:
				print(2)
		elif D == Q and C != P:
			if max(A[:r + 1]) <= min(D):
				print(1)
			else:
				print(2)
		elif max(C) <= min(A[k:]) or max(A[:r + 1]) <= min(D):
			print(1)
		else:
			print(2)


for i in range(int(input())):
	n = int(input())
	A = [int(k) for k in input().split()]
	s = input()
	S = 0
	N = 0
	for k in s:
		if k == 'N':
			N += 1
		else:
			S += 1
	if S == n and A != sorted(A) or (N == n and A != sorted(A)):
		print(-1)
	elif A == sorted(A):
		print(0)
	elif s[0] != s[-1]:
		print(1)
	else:
		z = 0
		d = sorted(A)
		S = A.index(d[-1])
		P = A.index(d[0])
		for k in range(n):
			if A[k] != d[k]:
				z += 1
				S = min(k, S)
				P = max(k, P)
				if k >= 1:
					d.append([s[k - 1], s[k]])
		S1 = 0
		P1 = 0
		for k in range(n):
			if k < S:
				if s[k] != s[P]:
					S1 = 1
			if k >= P:
				if s[k] != s[S]:
					P1 = 1
		if S1 == 1 or P1 == 1 or s[S] != s[P]:
			print(1)
		else:
			print(2)


import sys

def get_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	a = get_arr()
	s = input()
	b = []
	for i in range(n):
		b.append(a[i])
	b.sort()
	fl = -1
	for i in range(n):
		if a[i] != b[i]:
			fl = i
			break
	fl2 = -1
	for i in range(n - 1, -1, -1):
		if a[i] != b[i]:
			fl2 = i
			break
	if fl == -1:
		print(0)
		continue
	elif s[0] == 'N' and s[n - 1] == 'S' or (s[0] == 'S' and s[n - 1] == 'N'):
		print(1)
	else:
		n2 = 0
		s2 = 0
		for i in range(n):
			if s[i] == 'N':
				n2 = 1
			if s[i] == 'S':
				s2 = 1
		if n2 == 0 or s2 == 0:
			print(-1)
		else:
			if s[fl] == 'N':
				val = 0
				for i in range(fl2, n):
					if s[i] == 'S':
						print(1)
						val = 1
						break
				if val == 1:
					continue
			else:
				val = 0
				for i in range(fl2, n):
					if s[i] == 'N':
						print(1)
						val = 1
						break
				if val == 1:
					continue
			if s[fl2] == 'N':
				val = 0
				for i in range(fl, -1, -1):
					if s[i] == 'S':
						print(1)
						val = 1
						break
				if val == 1:
					continue
			else:
				val = 0
				for i in range(fl, -1, -1):
					if s[i] == 'N':
						print(1)
						val = 1
						break
				if val == 1:
					continue
			print(2)
			continue


def solve(n, arr, p):
	sorted_arr = sorted(arr)
	if arr == sorted_arr:
		return 0
	first_s = -1
	last_s = -1
	first_n = -1
	last_n = -1
	for i in range(n):
		if p[i] == 'S':
			if first_s == -1:
				first_s = i
			last_s = i
		else:
			if first_n == -1:
				first_n = i
			last_n = i
	for i in range(n):
		if arr[i] == sorted_arr[i]:
			continue
		if p[-1] != p[i]:
			return 1
		if p[i] == 'N':
			if first_s == -1:
				return -1
			if first_s < i:
				return 1
			return 2 if sorted(arr[:last_s + 1]) + arr[last_s + 1:] != sorted_arr else 1
		else:
			if first_n == -1:
				return -1
			if first_n < i:
				return 1
			return 2 if sorted(arr[:last_n + 1]) + arr[last_n + 1:] != sorted_arr else 1
	return 0
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	p = input()
	print(solve(n, arr, p))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	c = sorted(a)
	if c == a:
		print(0)
		continue
	if 0 in [s.count('N'), s.count('S')]:
		print(-1)
		continue
	l = None
	r = None
	for j in range(n):
		if c[j] != a[j]:
			r = j
			if l == None:
				l = j
	if s[l] != s[r]:
		print(1)
	elif s[l] == 'N':
		if 'S' in s[:l + 1] or 'S' in s[r:]:
			print(1)
			continue
		else:
			print(2)
	elif 'N' in s[:l + 1] or 'N' in s[r:]:
		print(1)
	else:
		print(2)


strng = lambda : input().split()[0]
inp = lambda : int(input())
mul = lambda : map(int, input().split())
jn = lambda x, l: x.join(map(str, l))
slst = lambda : list(input().split()[0])
silst = lambda : list(map(int, input().split()[0]))
lst = lambda : list(map(int, input().split()))
dd = lambda : defaultdict(lambda : 0)
import sys
input = sys.stdin.readline
from collections import defaultdict
from math import ceil, log, floor, sqrt, gcd, log10

def merge(a, lo, hi, m):
	tmp = []
	i = lo
	j = m + 1
	while i <= m and j <= hi:
		if a[i] > a[j]:
			tmp += [a[j]]
			j += 1
		else:
			tmp += [a[i]]
			i += 1
	while i <= m:
		tmp += [a[i]]
		i += 1
	while j <= hi:
		tmp += [a[j]]
		j += 1
	j = 0
	for i in range(lo, hi + 1):
		a[i] = tmp[j]
		j += 1

def msrt(arr, lo, hi):
	if lo < hi:
		m = (lo + hi) // 2
		msrt(arr, lo, m)
		msrt(arr, m + 1, hi)
		merge(arr, lo, hi, m)

def part(a, lo, hi):
	i = lo - 1
	j = 0
	while j < hi:
		if a[j] <= a[hi]:
			i += 1
			(a[j], a[i]) = (a[i], a[j])
		j += 1
	(a[i + 1], a[hi]) = (a[hi], a[i + 1])
	return i + 1

def qsrt(arr, lo, hi):
	if lo < hi:
		m = part(arr, lo, hi)
		print(m)
		qsrt(arr, lo, m - 1)
		qsrt(arr, m + 1, hi)
for _ in range(inp()):
	n = inp()
	a = lst()
	s = strng()
	da = defaultdict(lambda : 0)
	b = sorted(a)
	for i in range(n):
		da[s[i]] += 1
		if a[i] != b[i]:
			break
	else:
		print(0)
		continue
	if len(set(s)) <= 1:
		print(-1)
		continue
	if s[0] != s[n - 1] or len(da) == 2:
		print(1)
		continue
	flag = False
	for j in range(n - 1, i, -1):
		if s[j] not in da:
			flag = True
			break
		if a[j] != b[j]:
			break
	if flag:
		print(1)
	else:
		print(2)


t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	chars = [x for x in input()]
	num_north = sum([1 if x == 'N' else 0 for x in chars])
	if all((nums[x] <= nums[x + 1] for x in range(n - 1))):
		print(0)
	elif num_north == 0 or num_north == n:
		print(-1)
	else:
		first_north = -1
		last_north = -1
		first_south = -1
		last_south = -1
		for i in range(n):
			if chars[i] == 'N':
				first_north = i
				break
		for i in range(n):
			if chars[i] == 'S':
				first_south = i
				break
		for i in range(n - 1, -1, -1):
			if chars[i] == 'N':
				last_north = i
				break
		for i in range(n - 1, -1, -1):
			if chars[i] == 'S':
				last_south = i
				break
		one = nums[:first_north] + sorted(nums[first_north:last_south + 1]) + nums[last_south + 1:]
		two = nums[:first_south] + sorted(nums[first_south:last_north + 1]) + nums[last_north + 1:]
		if all((one[i] <= one[i + 1] for i in range(n - 1))) or all((two[i] <= two[i + 1] for i in range(n - 1))):
			print(1)
		else:
			print(2)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	s = input().strip()
	res = sorted(li[:])
	if res == li:
		print(0)
	elif s.count('S') == 0 or s.count('N') == 0:
		print(-1)
	elif s[0] + s[-1] == 'NS' or s[0] + s[-1] == 'SN':
		print(1)
	else:
		(s1, s2, n1, n2) = (-1, -1, -1, -1)
		for i in range(n):
			if s[i] == 'N':
				if n1 == -1:
					n1 = i
				else:
					n2 = i
			elif s1 == -1:
				s1 = i
			else:
				s2 = i
		if s2 == -1:
			s2 = s1
		if n2 == -1:
			n2 = n1
		if li[:n1] + sorted(li[n1:s2 + 1]) + li[s2 + 1:] == res or li[:s1] + sorted(li[s1:n2 + 1]) + li[n2 + 1:] == res:
			print(1)
		else:
			print(2)


for _ in range(int(input())):
	n = int(input())
	ai = list(map(int, input().split()))
	s = input()
	s1 = -1
	s2 = -1
	n1 = -1
	n2 = -1
	for i in range(n):
		if s[i] == 'S':
			s2 = i
		else:
			n2 = i
		if s[n - i - 1] == 'S':
			s1 = n - i - 1
		else:
			n1 = n - i - 1
	li = sorted(ai)
	if ai == li:
		print(0)
	elif s.count('N') == n or s.count('N') == 0:
		print(-1)
	elif ai[:s1] + sorted(ai[s1:n2 + 1]) + ai[n2 + 1:] == li or ai[:n1] + sorted(ai[n1:s2 + 1]) + ai[s2 + 1:] == li:
		print(1)
	else:
		print(2)


def solve(n, arr, s):
	a = list(sorted(arr))
	if arr == a or n == 1:
		return 0
	if len(set(s)) == 1:
		return -1
	(i, j) = (0, n - 1)
	while arr[i] == a[i]:
		i += 1
	while arr[j] == a[j]:
		j -= 1
	lefts = 'S' in s[:i + 1]
	leftn = 'N' in s[:i + 1]
	rights = 'S' in s[j:]
	rightn = 'N' in s[j:]
	if lefts and rightn or (leftn and rights):
		return 1
	return 2
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	s = input()
	print(solve(n, arr, s))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = input()
	k = l.copy()
	k.sort()
	if k == l:
		print(0)
	elif len(set(s)) == 1:
		print(-1)
	elif s[0] != s[-1]:
		print(1)
	else:
		c = s[-1]
		ind = 0
		for i in range(n):
			if l[i] != k[i]:
				ind = i
				break
		last = n - 1
		for i in range(n - 1, ind, -1):
			if k[i] != l[i]:
				last = i
				break
		c2 = s[last]
		flag = False
		for i in range(ind + 1):
			for j in range(last, n):
				if s[i] != s[j]:
					print(1)
					flag = True
					break
			if flag:
				break
		else:
			print(2)


def solve(A, S):
	arr = sorted(A)
	if arr == A:
		return 0
	n_count = S.count('N')
	s_count = S.count('S')
	if n_count == 0 or s_count == 0:
		return -1
	l = float('inf')
	r = 0
	left_N = False
	right_N = False
	left_S = False
	right_S = False
	for i in range(len(A)):
		if A[i] != arr[i]:
			l = min(l, i)
			r = max(r, i)
	for i in range(l + 1):
		if S[i] == 'N':
			left_N = True
		if S[i] == 'S':
			left_S = True
	for i in range(r, len(A)):
		if S[i] == 'N':
			right_N = True
		if S[i] == 'S':
			right_S = True
	if left_S and right_N or (left_N and right_S):
		return 1
	return 2
test_cases = int(input())
for i in range(int(test_cases)):
	n = int(input())
	A = list(map(int, input().split()))
	S = input()
	print(solve(A, S))


import sys

def check(A, first, last):
	A[first:last + 1] = sorted(A[first:last + 1])
	if A == sorted(A):
		return 1
	return 0

def solve(A, S):
	arr = sorted(A)
	if arr == A:
		return 0
	n_count = S.count('N')
	s_count = S.count('S')
	if n_count == 0 or s_count == 0:
		return -1
	d = {'leftN': 0, 'leftS': 0, 'rightN': 0, 'rightS': 0}
	(l, r) = (10 ** 6, 0)
	n = len(S)
	temparr = arr
	s = S
	a = A
	for i in range(n):
		if temparr[i] != a[i]:
			l = min(l, i)
			r = max(r, i)
	for i in range(l + 1):
		if s[i] == 'N':
			d['leftN'] += 1
		if s[i] == 'S':
			d['leftS'] += 1
	for i in range(r, n):
		if s[i] == 'N':
			d['rightN'] += 1
		if s[i] == 'S':
			d['rightS'] += 1
	if d['leftS'] > 0 and d['rightN'] > 0 or (d['rightS'] > 0 and d['leftN'] > 0):
		return 1
	else:
		return 2
t = int(input())
for i in range(int(t)):
	n = int(input())
	A = list(map(int, input().split()))
	S = input()
	print(solve(A, S))


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	temparr = sorted(a)
	s = input()
	if temparr == a:
		print(0)
		continue
	if s.count('S') == n or s.count('N') == n:
		print(-1)
		continue
	d = {'leftN': 0, 'leftS': 0, 'rightN': 0, 'rightS': 0}
	(l, r) = (10 ** 6, 0)
	for i in range(n):
		if temparr[i] != a[i]:
			l = min(l, i)
			r = max(r, i)
	for i in range(l + 1):
		if s[i] == 'N':
			d['leftN'] += 1
		if s[i] == 'S':
			d['leftS'] += 1
	for i in range(r, n):
		if s[i] == 'N':
			d['rightN'] += 1
		if s[i] == 'S':
			d['rightS'] += 1
	if d['leftS'] > 0 and d['rightN'] > 0 or (d['rightS'] > 0 and d['leftN'] > 0):
		print(1)
	else:
		print(2)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = list(input())
	if all((a[i - 1] <= a[i] for i in range(1, n))):
		print(0)
		continue
	n_ct = s.count('N')
	if n_ct == n or n_ct == 0:
		print(-1)
		continue
	(left, right) = (n + 1, -1)
	b = sorted(a)
	for (i, (av, bv)) in enumerate(zip(a, b)):
		if av != bv:
			left = i
			break
	for (i, (av, bv)) in enumerate(zip(a[::-1], b[::-1])):
		if av != bv:
			right = n - 1 - i
			break
	(lf, rf) = (False, False)
	for i in range(left):
		if s[i] != s[right]:
			lf = True
			break
	for i in range(right, n):
		if s[i] != s[left]:
			rf = True
			break
	if s[left] != s[right] or lf or rf:
		print(1)
		continue
	print(2)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	string = input()
	cnt_s = string.count('S')
	cnt_n = string.count('N')
	sorted_a = list(sorted(a))
	if a == sorted_a:
		print(0)
	elif cnt_s == 0 or cnt_n == 0:
		print(-1)
	else:
		for i in range(n):
			if sorted_a[i] != a[i]:
				diff_index_start = i
				break
		for j in range(n - 1, -1, -1):
			if sorted_a[j] != a[j]:
				diff_index_end = j
				break
		left = string[:diff_index_start + 1]
		right = string[diff_index_end:]
		if 'N' in left and 'S' in right or ('S' in left and 'N' in right):
			ans = 1
		else:
			ans = 2
		print(ans)


t = int(input())

def solve(ar, pol):
	ref = sorted(ar)
	if ar == ref:
		return 0
	if len(set(pol)) == 1:
		return -1
	n = len(ar)
	for i in range(n):
		if ar[i] != ref[i]:
			break
	for j in range(n - 1, -1, -1):
		if ar[j] != ref[j]:
			break
	for k in range(i + 1):
		for l in range(j, n):
			if pol[k] != pol[l] and k < l:
				return 1
	return 2
for _ in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	pol = list(input())
	print(solve(x, pol))


for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	P = input()
	SA = sorted(A)
	if A == SA:
		print(0)
		continue
	elif not (P.count('N') and P.count('S')):
		print(-1)
		continue
	elif P[0] != P[-1]:
		print(1)
		continue
	(s, e) = (0, N - 1)
	while s < e:
		if P[s] != P[0] or P[e] != P[0]:
			break
		if A[s] == SA[s]:
			s += 1
		elif A[e] == SA[e]:
			e -= 1
		else:
			break
	if P[s] != P[0] or P[e] != P[0]:
		print(1)
	else:
		print(2)


def disturbance(l, p, n):
	(st, en) = (-1, 0)
	for i in range(n):
		if l[i] != p[i]:
			if st == -1:
				st = i
			else:
				en = i
	return (st, en)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = str(input())
	p = []
	for i in l:
		p.append(i)
	p.sort()
	n_c = s.count('N')
	if p != l:
		if n_c == n or n_c == 0:
			print(-1)
		else:
			(start, end) = disturbance(l, p, n)
			if s[start] != s[end]:
				print(1)
			else:
				ans2 = 10000
				for i in range(start, end + 1):
					if s[i] != s[start]:
						ans2 = 2
						break
				(nl, sl) = (0, 0)
				for i in range(start + 1):
					if s[i] == 'N':
						nl = 1
					elif s[i] == 'S':
						sl = 1
				(nr, sr) = (0, 0)
				for j in range(end, n):
					if s[j] == 'N':
						nr = 1
					elif s[j] == 'S':
						sr = 1
				ans3 = 10000
				if nl & sr == 1 or sl & nr == 1:
					ans3 = 1
				print(min(ans2, ans3))
	else:
		print(0)


def check(A, first, last):
	A[first:last + 1] = sorted(A[first:last + 1])
	if A == sorted(A):
		return 1
	return 0

def solve(A, S, N):
	if A == sorted(A):
		print(0)
		return
	countN = 0
	for ch in S:
		if ch == 'N':
			countN += 1
	if countN == 0 or countN == N:
		print(-1)
		return
	(firstN, lastN, firstS, lastS) = (-1, -1, -1, -1)
	for i in range(N):
		if S[i] == 'N':
			if firstN == -1:
				firstN = i
			lastN = i
		else:
			if firstS == -1:
				firstS = i
			lastS = i
	ans = 2
	if check(A[:], firstN, lastS) == 1 or check(A[:], firstS, lastN) == 1:
		ans = 1
	print(ans)
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	S = input()
	solve(A, S, N)


try:
	t = int(input())
	for q in range(t):
		n = int(input())
		l = list(map(int, input().split()))
		s = input()
		a = []
		flag = 0
		left = 0
		right = n - 1
		for v in range(n - 1):
			if s[v] != s[v + 1]:
				flag += 1
		for j in l:
			a.append(j)
		l.sort()
		index = []
		for i in range(n):
			if a[i] != l[i]:
				index.append(i)
		f = 0
		if len(index) != 0:
			for z in range(min(index) + 1):
				if f == 1:
					break
				for y in range(n - 1, max(index) - 1, -1):
					if f == 1:
						break
					if s[z] != s[y]:
						print(1)
						f = 1
			if f == 0:
				if flag == 0:
					print(-1)
				else:
					print(2)
		else:
			print(0)
except:
	pass


def res1(n, arr, stri):
	cnt1 = 0
	cnt2 = 0
	for i in range(n):
		if stri[i] == 'N':
			cnt1 += 1
		else:
			cnt2 += 1
	sarr = sorted(arr)
	if cnt1 == n and sarr != arr or (cnt2 == n and sarr != arr):
		return -1
	if sarr == arr:
		return 0
	if stri[0] != stri[-1]:
		return 1
	s = arr.index(sarr[-1])
	p = arr.index(sarr[0])
	p = 0
	for i in range(n):
		if arr[i] != sarr[i]:
			s = min(s, i)
			p = max(p, i)
	s1 = 0
	p1 = 0
	for k in range(n):
		if k < s:
			if stri[k] != stri[p]:
				s1 = 1
		if k >= p:
			if stri[k] != stri[s]:
				p1 = 1
	if s1 == 1 or p1 == 1 or stri[s] != stri[p]:
		return 1
	else:
		return 2
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	stri = input()
	print(res1(n, arr, stri))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	b = a.copy()
	b.sort()
	if a == b:
		print(0)
	elif len(set(s)) == 1:
		print(-1)
	else:
		b1 = 0
		for j in range(0, n - 1):
			if s[-1] == 'S':
				if s[j] == 'N':
					b1 = j
					break
			elif s[-1] == 'N':
				if s[j] == 'S':
					b1 = j
					break
		l1 = a[b1:]
		l1.sort()
		l2 = a[:b1]
		l3 = l2 + l1
		b2 = 0
		for j in range(n - 1, 0, -1):
			if s[0] == 'S':
				if s[j] == 'N':
					b2 = j
					break
			elif s[0] == 'N':
				if s[j] == 'S':
					b2 = j
					break
		l4 = a[:b2 + 1]
		l4.sort()
		l5 = a[b2 + 1:]
		l6 = l4 + l5
		ans1 = 0
		ans2 = 0
		if l3 == b:
			ans1 = 1
		if l3 != b:
			ans1 = 2
		if l6 == b:
			ans2 = 1
		if l6 != b:
			ans2 = 2
		print(min(ans1, ans2))


t = int(input())
while t:
	n = int(input())
	li = list(map(int, input().strip().split()))
	s = input()
	lii = li.copy()
	lii.sort()
	ans = 2
	if lii == li:
		ans = 0
	elif len(set(s)) == 1:
		ans = -1
	elif s[0] == s[n - 1] and len(set(s)) > 1:
		lis = list(s)
		for j in range(n - 1, 0, -1):
			if lis[j] != lis[0]:
				var = j
				break
		for i in range(n):
			if lis[i] != lis[n - 1]:
				var2 = i
				break
		if lii[var + 1:] == li[var + 1:]:
			ans = 1
		elif lii[0:var2] == li[0:var2]:
			ans = 1
	elif s[0] != s[n - 1]:
		ans = 1
	print(ans)
	t -= 1


T = int(input())
for _ in range(T):
	n = int(input())
	lo = list(map(int, input().split()))
	s = sorted(lo)
	c = list(input())
	r = -1
	if lo == s:
		r = 0
	if 'N' in c and 'S' in c:
		if lo == s:
			r = 0
		elif c[0] != c[-1]:
			r = 1
		else:
			front = n
			rear = 0
			for i in range(n):
				if lo[i] != s[i]:
					front = min(i, front)
					rear = max(i, rear)
			f = 0
			for i in range(front + 1):
				if c[i] != c[-1]:
					f = 1
					break
			for i in range(rear, n):
				if c[i] != c[-1]:
					f = 1
					break
			if f:
				r = 1
			else:
				r = 2
	print(r)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input().strip()
	b = sorted(a)
	if b == a or len(a) == 1:
		print(0)
	else:
		st = 0
		for i in range(n):
			if a[i] == b[i]:
				pass
			else:
				st = i
				break
		ed = n - 1
		for i in range(ed, st - 1, -1):
			if a[i] == b[i]:
				pass
			else:
				ed = i
				break
		if s[st] != s[ed]:
			print(1)
		elif s[st] == 'N':
			pres = 0
			for i in range(st):
				if s[i] == 'S':
					pres = 1
			for i in range(ed + 1, n):
				if s[i] == 'S':
					pres = 1
			if pres:
				print(1)
			else:
				for i in range(st + 1, ed):
					if s[i] == 'S':
						pres = 1
				if pres:
					print(2)
				else:
					print(-1)
		else:
			pres = 0
			for i in range(st):
				if s[i] == 'N':
					pres = 1
			for i in range(ed + 1, n):
				if s[i] == 'N':
					pres = 1
			if pres:
				print(1)
			else:
				for i in range(st + 1, ed):
					if s[i] == 'N':
						pres = 1
				if pres:
					print(2)
				else:
					print(-1)


t = int(input())
for _ in range(t):
	(ct, n) = (0, int(input()))
	a = list(map(int, input().split()))
	(pre, s, f) = (0, input(), True)
	for i in a:
		if i < pre:
			f = False
			break
		pre = i
	if f:
		print(0)
		continue
	for i in s:
		if i == 'S':
			ct += 1
	if ct == n or ct == 0:
		print(-1)
		continue
	b = sorted(a)
	(mini, maxi) = (10 ** 10, 0)
	for (i, (av, bv)) in enumerate(zip(a, b)):
		if av != bv:
			mini = min(mini, i)
			maxi = max(maxi, i)
	(f1, f2) = (False, False)
	for i in s[:mini]:
		if i != s[maxi]:
			f1 = True
	for i in s[maxi:]:
		if i != s[mini]:
			f2 = True
	if s[mini] != s[maxi] or f1 or f2:
		print(1)
	else:
		print(2)


def MostMisplaced(arr, arrSorted):
	for x in range(len(arr)):
		if arr[x] != arrSorted[x]:
			return x
	return None

def insideRange(val, myRange):
	if val >= myRange[0] and val <= myRange[1]:
		return True
	else:
		return False

def areIn(leftMost, rightMost, givenRange):
	if insideRange(leftMost, givenRange) and insideRange(rightMost, givenRange):
		return True
	return False

def minCost(arr, pole):
	arrSorted = arr[:]
	arrSorted.sort()
	leftMisplace = MostMisplaced(arr, arrSorted)
	if leftMisplace == None:
		return 0
	rightMisplace = len(arr) - 1 - MostMisplaced(arr[::-1], arrSorted[::-1])
	try:
		leftMostN = pole.index('N')
		leftMostS = pole.index('S')
		rightMostN = len(pole) - 1 - pole[::-1].index('N')
		rightMostS = len(pole) - 1 - pole[::-1].index('S')
		NS = (leftMostN, rightMostS)
		SN = (leftMostS, rightMostN)
		if areIn(leftMisplace, rightMisplace, NS) or areIn(leftMisplace, rightMisplace, SN):
			return 1
		else:
			return 2
	except:
		return -1
T = int(input())
for i in range(T):
	N = int(input())
	arr = [int(x) for x in input().split()]
	pole = [x for x in input()]
	print(minCost(arr, pole))


from sys import stdin
from collections import defaultdict as dd, deque as dq
from heapq import heappush as hpush, heappop as hpop
from bisect import bisect_left as bl, bisect_right as br
from random import randint
from math import sqrt, ceil, floor
from time import time

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def text():
	return stdin.readline().rstrip()

def num():
	return int(text())

def mp(dt):
	return map(dt, stdin.readline().split())

def array(dt):
	return list(mp(dt))

def SieveOfEratosthenes(n, prime):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1

def timer_func(func):

	def wrap_func(*args, **kwargs):
		t1 = time()
		result = func(*args, **kwargs)
		t2 = time()
		return result
	return wrap_func

@timer_func
def solve():
	t = num()
	while t > 0:
		n = num()
		a = array(int)
		s = text()
		(no, so) = (0, 0)
		for i in s:
			if i == 'N':
				no += 1
			else:
				so += 1
		sa = sorted(a)
		c = -1
		e = -1
		for i in range(n):
			if sa[i] != a[i]:
				if c == -1:
					c = i
				e = i
		if c == -1:
			print(0)
		elif no == 0 or so == 0:
			print(-1)
		else:
			(no, so) = (0, 0)
			for i in range(c, -1, -1):
				if s[i] == 'N':
					no += 1
				else:
					so += 1
			for i in range(e, n):
				if s[i] == 'N':
					no += 1
				else:
					so += 1
			if no == 0 or so == 0:
				print(2)
			else:
				print(1)
		t -= 1
solve()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	s = input()
	if sorted(arr) == arr:
		print(0)
	elif 'N' not in s or 'S' not in s:
		print(-1)
	else:
		begin = -1
		end = -1
		temp = sorted(arr)
		for i in range(n):
			if temp[i] != arr[i]:
				begin = i
				break
		for i in range(n - 1, -1, -1):
			if temp[i] != arr[i]:
				end = i
				break
		check = s[:begin + 1] + s[end:]
		if 'N' in check and 'S' in check:
			print(1)
		else:
			print(2)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	d = list(input())
	if a == b:
		print(0)
		continue
	if d.count('N') == n or d.count('N') == 0:
		print('-1')
		continue
	start = -1
	end = -1
	for i in range(n):
		if a[i] != b[i] and start == -1:
			start = i
			end = i
		elif a[i] != b[i]:
			end = i
	now = d[:start + 1]
	now1 = d[end:]
	now = now + now1
	now = set(now)
	if len(now) == 2:
		print(1)
	else:
		print(2)


_ = int(input())
while _:
	_ -= 1
	n = int(input())
	l = list(map(int, input().split()))
	s = input()
	nl = sorted(l)
	if l == nl:
		print(0)
	elif 'N' not in s or 'S' not in s:
		print(-1)
	elif s[0] != s[-1]:
		print(1)
	else:
		fn = s.index('N')
		fs = s.index('S')
		ln = n - s[::-1].index('N')
		ls = n - s[::-1].index('S')
		if l[:fn] + sorted(l[fn:ls]) + l[ls:] == nl or l[:fs] + sorted(l[fs:ln]) + l[ln:] == nl:
			print(1)
		else:
			print(2)


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	pole = input()
	o = sorted(nums)
	pre = []
	for (i, item) in enumerate(pole):
		k = 0
		if item == 'N':
			k = 1
		if i:
			k += pre[i - 1]
		pre.append(k)
	index = []
	for (i, item) in enumerate(nums):
		if item != o[i]:
			index.append(i)
	if nums == o:
		print(0)
		continue
	elif pole == 'N' * n or pole == 'S' * n:
		print(-1)
		continue
	if pole[index[0]] != pole[index[-1]]:
		print(1)
	elif pole[index[0]] == 'N':
		if pre[index[0]] < index[0] + 1 or pre[-1] - pre[index[-1]] < len(o) - index[-1] - 1:
			print(1)
		else:
			print(2)
	elif pre[index[0]] > 0 or pre[-1] - pre[index[-1]] > 0:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	polarity = input()
	if sorted(a) == a:
		print(0)
	elif len(set(polarity)) == 1:
		print(-1)
	elif polarity[0] != polarity[-1]:
		print(1)
	else:
		f = 0
		i = 0
		p1 = 0
		p2 = 0
		while i < n:
			if f == 0 and polarity[i] == 'N':
				f = 1
				p1 = i
			if polarity[i] == 'S':
				p2 = i
			i += 1
		t1 = a[:p1] + sorted(a[p1:p2 + 1]) + a[p2 + 1:]
		f = 0
		i = 0
		p1 = 0
		p2 = 0
		while i < n:
			if f == 0 and polarity[i] == 'S':
				f = 1
				p1 = i
			if polarity[i] == 'N':
				p2 = i
			i += 1
		t2 = a[:p1] + sorted(a[p1:p2 + 1]) + a[p2 + 1:]
		if sorted(a) == t1 or sorted(a) == t2:
			print(1)
		else:
			print(2)


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

def li():
	return list(mi())

def ni():
	return int(input())

def si():
	return str(input())

def isSorted(A):
	if not A:
		return True
	temp = list(A)
	temp.sort()
	return temp == A
for t in range(ni()):
	N = ni()
	A = li()
	S = si()
	new = ''
	for i in S:
		if i == 'S':
			new += '0'
		else:
			new += '1'
	S = new
	if isSorted(A):
		print(0)
		continue
	if S == '0' * N or S == '1' * N:
		print(-1)
		continue
	if S[0] != S[-1]:
		print(1)
		continue
	st = list(A)
	st.sort()
	temp = S[::-1]
	first = S.find(str(int(S[0]) ^ 1))
	last = N - 1 - temp.find(str(int(S[0]) ^ 1))
	if st[:first] == A[:first] or st[last + 1:] == A[last + 1:]:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	opp = {'S': 'N', 'N': 'S'}
	temp = sorted(a)
	if a == temp:
		print(0)
	elif s[0] != s[-1]:
		print(1)
	elif opp[s[0]] not in s:
		print(-1)
	else:
		for i in range(n):
			if a[i] != temp[i]:
				s1 = i
				break
		for i in range(n - 1, -1, -1):
			if a[i] != temp[i]:
				s2 = i
				break
		if s[s1] != s[s2] or opp[s[s1]] in s[:s1] + s[s2 + 1:]:
			print(1)
		else:
			print(2)


def solve(n, s, nums):
	if sorted(nums) == nums:
		return 0
	if 'N' not in s or 'S' not in s:
		return -1
	temp = nums.copy()
	if s[0] == 'N':
		idx = -1
		for i in range(n):
			if s[i] == 'S':
				idx = i
		temp[:idx + 1] = sorted(temp[:idx + 1])
	else:
		idx = -1
		for i in range(n):
			if s[i] == 'N':
				idx = i
		temp[:idx + 1] = sorted(temp[:idx + 1])
	if temp == sorted(temp):
		return 1
	temp = nums.copy()
	if s[-1] == 'N':
		idx = -1
		for i in range(n - 1, -1, -1):
			if s[i] == 'S':
				idx = i
		temp[idx:] = sorted(temp[idx:])
	else:
		idx = -1
		for i in range(n - 1, -1, -1):
			if s[i] == 'N':
				idx = i
		temp[idx:] = sorted(temp[idx:])
	if temp == sorted(temp):
		return 1
	return 2
for t in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	s = input()
	print(solve(n, s, li))


def isSorted(nums):
	for i in range(1, len(nums)):
		if nums[i - 1] > nums[i]:
			return False
	return True

def solve(n, s, nums):
	if isSorted(nums):
		return 0
	if 'N' not in s or 'S' not in s:
		return -1
	temp = nums.copy()
	i = s.find('N')
	j = s.rfind('S')
	if i < j:
		temp[i:j + 1] = sorted(temp[i:j + 1])
		if isSorted(temp):
			return 1
	temp = nums.copy()
	i = s.find('S')
	j = s.rfind('N')
	if i < j:
		temp[i:j + 1] = sorted(temp[i:j + 1])
		if isSorted(temp):
			return 1
	return 2
for t in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	s = input()
	print(solve(n, s, li))


try:
	for t in range(int(input())):
		firstshank = int(input())
		okaydear = list(map(int, input().split()))
		starting = input()
		sorts = sorted(okaydear)
		if okaydear == sorts:
			print(0)
		else:
			fin = 0
			phelanhifi = firstshank - 1
			for i in range(firstshank):
				if okaydear[i] != sorts[i]:
					fin = i
					break
			for i in range(firstshank - 1, -1, -1):
				if okaydear[i] != sorts[i]:
					la = i
					break
			cc = True
			cc = set()
			for i in range(fin + 1):
				cc.add(starting[i])
			for i in range(firstshank - 1, la - 1, -1):
				cc.add(starting[i])
			if len(cc) == 2:
				print(1)
			elif starting.count(starting[0]) == firstshank:
				print(-1)
			else:
				print(2)
except EOFError:
	pass


alp = 'abcdefghijklmnopqrstuvwxyz'
ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
from math import ceil, sqrt, factorial, log
from collections import deque
from bisect import bisect_left
import sys
input = lambda : sys.stdin.readline().strip()
lis = lambda : list(map(int, input().split()))
sin = lambda : int(input())
many = lambda : map(int, input().split())
mod = 10 ** 9 + 7
dp = [[0] * 51 for i in range(51)]
import math

def solve():
	n = sin()
	l = lis()
	s = input()
	p = l[:]
	p.sort()
	if p == l:
		print(0)
		return
	if s[0] != s[-1]:
		print(1)
		return
	se = set(s)
	if len(se) == 1:
		print(-1)
		return
	ind1 = -1
	c1 = set()
	for i in range(n):
		c1.add(s[i])
		if p[i] != l[i]:
			ind1 = i
			break
	ind2 = -1
	c2 = set()
	for i in range(n - 1, -1, -1):
		c2.add(s[i])
		if p[i] != l[i]:
			ind2 = i
			break
	if 'N' in c1 and 'S' in c2 or ('N' in c2 and 'S' in c1):
		print(1)
		return
	print(2)
testisisisisisis = int(input())
for testis in range(testisisisisisis):
	solve()


def arraySortedOrNot(arr, N):
	if N == 0 or N == 1:
		return True
	for i in range(1, N):
		if arr[i - 1] > arr[i]:
			return False
	return True
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	polarityStr = input()
	boolSort = arraySortedOrNot(A, len(A))
	if 'S' in polarityStr and 'N' in polarityStr:
		if boolSort:
			print(0)
		elif polarityStr[0] != polarityStr[N - 1]:
			print(1)
		else:
			a = 1
			b = N - 2
			while True:
				if polarityStr[a] != polarityStr[0]:
					break
				a = a + 1
			while True:
				if polarityStr[b] != polarityStr[N - 1]:
					break
				b = b - 1
			l1 = sorted(A)
			if A[:a] == l1[:a] or A[b + 1:] == l1[b + 1:]:
				print(1)
			else:
				print(2)
	elif boolSort:
		print(0)
	else:
		print(-1)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))

def func():
	n = inp()
	l = seq()
	s = strng()
	ls = sorted(l)
	if l == ls:
		return 0
	elif s[0] != s[-1]:
		return 1
	elif not 'N' in s or not 'S' in s:
		return -1
	posmin = -1
	posmax = -1
	for i in range(n):
		if l[i] != ls[i]:
			posmin = i
			break
	for i in range(n - 1, -1, -1):
		if l[i] != ls[i]:
			posmax = i
			break
	if s[posmin] != s[posmax]:
		return 1
	for i in range(posmin):
		if s[i] != s[posmin]:
			return 1
	for i in range(posmax, n):
		if s[i] != s[posmax]:
			return 1
	return 2
t = inp()
for i in range(t):
	print(func())


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = input()
	if 'N' in s and 'S' in s:
		if l == sorted(l):
			print('0')
		else:
			a = 0
			b = n - 1
			if s[a] != s[b]:
				print('1')
			else:
				a = 1
				b = n - 2
				while True:
					if s[a] != s[0]:
						break
					a = a + 1
				while True:
					if s[b] != s[n - 1]:
						break
					b = b - 1
				l1 = sorted(l)
				if l[:a] == l1[:a] or l[b + 1:] == l1[b + 1:]:
					print('1')
				else:
					print('2')
	elif l == sorted(l):
		print('0')
	else:
		print('-1')


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	s = input()
	ele = s[0]
	c = 0
	lst1 = lst.copy()
	lst1.sort()
	if lst1 == lst:
		print(0)
	else:
		for j in range(1, n):
			if s[j] != ele:
				c += 1
				break
		if c == 0:
			print(-1)
		else:
			ns = 0
			sn = 0
			n1 = s.index('N')
			s1 = n - s[::-1].index('S') - 1
			if s1 > n1:
				l1 = s1 - n1
			else:
				l1 = 0
			n2 = n - s[::-1].index('N') - 1
			s2 = s.index('S')
			if n2 > s2:
				l2 = n2 - s2
			else:
				l2 = 0
			c = 0
			lsta = lst[:n1]
			lstb = lst[n1:s1 + 1]
			lstc = lst[s1 + 1:]
			lstb.sort()
			lstf = lsta + lstb + lstc
			if lstf == lst1:
				c += 1
			lsta = lst[:s2]
			lstb = lst[s2:n2 + 1]
			lstc = lst[n2 + 1:]
			lstb.sort()
			lstf = lsta + lstb + lstc
			if lstf == lst1:
				c += 1
			lsta = lst[:s2]
			lstb = lst[s2:n2 + 1]
			lstc = lst[n2 + 1:]
			lstb.sort()
			lstf = lsta + lstb + lstc
			if lstf == lst1:
				c += 1
			lsta = lst[:n1]
			lstb = lst[n1:s1 + 1]
			lstc = lst[s1 + 1:]
			lstb.sort()
			lstf = lsta + lstb + lstc
			if lstf == lst1:
				c += 1
			if c > 0:
				print(1)
			else:
				start = -1
				pol = 'a'
				for a in range(1, n):
					if lst[a] < lst[a - 1]:
						start = a - 1
						pol = s[a - 1]
						break
				end = -1
				for l in range(n - 1, start, -1):
					if s[l] != pol:
						end = l
				lsta = lst[:start]
				lstb = lst[start:end + 1]
				lstc = lst[end + 1:]
				lstb.sort()
				lstf = lsta + lstb + lstc
				if lstf == lst1:
					print(1)
				else:
					print(2)


from math import *
from collections import *
import os
from io import BytesIO, IOBase
import sys
from bisect import *
from heapq import *
MOD = 1000000007

def binpow(a, b, m):
	a %= m
	x = 1
	while b > 0:
		if b & 1:
			x = x * a % m
		a = a * a % m
		b >>= 1
	return x

def binser(arr, l, r, x):
	while l < r:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	return mid

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

def sod(n):
	l = list(str(n))
	s = 0
	for i in l:
		s += int(i)
	return s

def prime_factors(num):
	l = []
	if num % 2:
		l.append(2)
	while num % 2 == 0:
		num = num / 2
	for i in range(3, int(sqrt(num)) + 1, 2):
		if not num % i:
			l.append(i)
		while num % i == 0:
			num = num / i
	if num > 2:
		l.append(num)
	return l

def factmod(n, p):
	f = defaultdict(int)
	f[0] = 1
	for i in range(1, n + 1):
		f[i] = f[i - 1] * i % MOD
	return f

def largestPower(n, p):
	x = 0
	while n:
		n //= p
		x += n
	return x

def modFact(n, p):
	if n >= p:
		return 0
	res = 1
	isPrime = [1] * (n + 1)
	i = 2
	while i * i <= n:
		if isPrime[i]:
			for j in range(2 * i, n, i):
				isPrime[j] = 0
		i += 1
	for i in range(2, n):
		if isPrime[i]:
			k = largestPower(n, i)
			res = res * binpow(i, k, p) % p
	return res

def drec(x, y):
	if y == x + 1:
		return 'R'
	if y == x - 1:
		return 'L'
	if x < y:
		return 'D'
	return 'U'

def cellhash(x, y):
	return (x - 1) * m + y

def bins(l, x, n):
	i = bisect_left(l, x)
	if i < n:
		return i
	if i:
		return i - 1
	else:
		return n

def cond(l):
	for i in range(len(l) - 1):
		if l[i] == str(int(l[i + 1]) - 1):
			return False
	return True

def isvowel(s):
	if s in list('aeiou'):
		return 1
	return 0

def countOdd(L, R):
	N = (R - L) // 2
	if R % 2 != 0 or L % 2 != 0:
		N += 1
	return N

def tst(A, B, C):
	return (A | B) & (B | C) & (C | A)

def palcheck(n, s):
	(i, j) = (0, n - 1)
	while i <= j:
		if s[i] == s[j]:
			return False
		i += 1
		j -= 1
	return True

def sakurajima(n):
	if n < 9:
		n = 10
	l = [0]
	for i in range(1, n + 1):
		if i % 2:
			l.append(i)
		else:
			l.append(2)
	for i in range(3, int(n ** 0.5) + 1, 2):
		if l[i] == i:
			for j in range(i * i, n + 1, i):
				if l[j] == j:
					l[j] = i
	return l

def getfact(x):
	ret = []
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return set(ret)

def prchck(n):
	l = [1] * (n + 1)
	l[1] = 0
	for i in range(2, n + 1):
		for j in range(2, int(sqrt(n)) + 1):
			if j % i == 0:
				l[j] = 1
	return l

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

def bfs(src, dest, ajl, vis):
	q = deque([src])
	vis[src] = True
	while q:
		i = q.popleft()
		if i == dest:
			return True
		for j in ajl[i]:
			if not vis[j]:
				vis[j] = True
				q.append(j)
	return False

class DisjSet:

	def __init__(self, n):
		self.size = defaultdict(int)
		self.parent = defaultdict(str)

	def find(self, x):
		if self.parent[x] != x:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def Union(self, x, y):
		xset = self.find(x)
		yset = self.find(y)
		if xset == yset:
			return
		if self.size[xset] < self.size[yset]:
			self.parent[xset] = yset
			self.size[yset] += self.size[xset]
		else:
			self.parent[yset] = xset
			self.size[xset] += self.size[yset]

def broly(src, ajl, vis, ans):
	q = deque([src])
	while q:
		i = q.popleft()
		if not vis[i]:
			ans.append(i)
		vis[i] = True
		for j in ajl[i]:
			if not vis[j]:
				q.append(j)

def dfs(i, ajl, vis, k, par):
	vis[i] = True
	if not k:
		return
	for j in ajl[i]:
		if k:
			print(par, j)
		if not vis[j]:
			dfs(j, ajl, vis, k - 1, par)

def panda(n, l, s):
	x = s.count('N')
	print
	l1 = sorted(l)
	if l == l1:
		return 0
	if not x or x == n:
		return -1
	fl = 0
	if s[0] != s[-1]:
		return 1
	(i, j) = (0, n - 1)
	(fi, fj) = (0, 0)
	while i < j:
		if l[i] != l1[i]:
			if not fi:
				fi = 1
		else:
			i += 1
		if l[j] != l1[j]:
			if not fj:
				fj = 1
		else:
			j -= 1
		if fi and fj:
			break
	for i1 in range(i):
		if s[i1] != s[i1 + 1]:
			return 1
	for j1 in range(n - 1, j, -1):
		if s[j1] != s[j1 - 1]:
			return 1
	if i >= j:
		return 1
	if s[i] == s[j]:
		return 2
	return 1
t = 1
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = input()
	print(panda(n, l, s))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	s = input()
	arr1 = []
	arr1 = arr.copy()
	arr1.sort()
	t1 = 0
	t2 = 0
	for i in range(n):
		if arr[n - 1 - i] != arr1[n - 1 - i] and t2 == 0:
			tester2 = n - 1 - i
			t2 = 1
		if arr[i] != arr1[i] and t1 == 0:
			tester1 = i
			t1 = 1
		if t1 == 1 and t2 == 1:
			break
	if arr1 == arr:
		print(0)
	elif len(set(s)) == 1:
		print(-1)
	elif s[0] != s[n - 1]:
		print(1)
	elif set(s[:tester1 + 1]) == set(s[tester2:]) and len(set(s[:tester1 + 1])) == 2:
		print(1)
	elif set(s[:tester1 + 1]) != set(s[tester2:]):
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	st = list(input())
	f = []
	res = sorted(arr)
	for i in range(0, n):
		if arr[i] != res[i]:
			f.append(i)
	com = st[0]
	flag = 0
	for i in st:
		if i != com:
			flag = 1
	if len(f) == 0:
		print(0)
	elif flag == 0:
		print(-1)
	else:
		r = len(f)
		flag1 = 0
		for i in range(0, f[0] + 1):
			for j in range(n - 1, f[r - 1] - 1, -1):
				if st[i] != st[j]:
					print(1)
					flag1 = 1
					break
			if flag1 == 1:
				break
		if flag1 == 0:
			print(2)


try:
	for t in range(int(input())):
		number = int(input())
		ant = list(map(int, input().split()))
		starting = input()
		sorts = sorted(ant)
		if ant == sorts:
			print(0)
		else:
			fin = 0
			last = number - 1
			for i in range(number):
				if ant[i] != sorts[i]:
					fin = i
					break
			for i in range(number - 1, -1, -1):
				if ant[i] != sorts[i]:
					la = i
					break
			o = True
			o = set()
			for i in range(fin + 1):
				o.add(starting[i])
			for i in range(number - 1, la - 1, -1):
				o.add(starting[i])
			if len(o) == 2:
				print(1)
			elif starting.count(starting[0]) == number:
				print(-1)
			else:
				print(2)
except EOFError:
	pass


for _ in range(int(input())):
	N = int(input())
	l = list(map(int, input().split()))
	so = sorted(l)
	c = list(input())
	ans = -1
	if l == so:
		ans = 0
	if 'N' in c and 'S' in c:
		if l == so:
			ans = 0
		elif c[0] != c[-1]:
			ans = 1
		else:
			front = N
			rear = 0
			for i in range(N):
				if l[i] != so[i]:
					front = min(i, front)
					rear = max(i, rear)
			flag = 0
			for i in range(front + 1):
				if c[i] != c[-1]:
					flag = 1
					break
			for i in range(rear, N):
				if c[i] != c[-1]:
					flag = 1
					break
			if flag:
				ans = 1
			else:
				ans = 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	s = input()
	sorted_lst = sorted(lst)
	if n == 1:
		print(0)
	elif lst != sorted_lst:
		if s[0] != s[-1]:
			print(1)
		elif s == 'N' * n or s == 'S' * n:
			print(-1)
		else:
			for i in range(n):
				if lst[i] != sorted_lst[i]:
					start = i
					break
			for i in range(n - 1, -1, -1):
				if lst[i] != sorted_lst[i]:
					end = i
					break
			if s[start] != s[end]:
				print(1)
			else:
				for i in range(start):
					if s[i] != s[end]:
						print(1)
						break
				else:
					for i in range(end, n):
						if s[i] != s[start]:
							print(1)
							break
					else:
						print(2)
	else:
		print(0)


n_test_cases = int(input())
results = []
for _ in range(n_test_cases):
	n_ints = int(input())
	A = [int(x) for x in input().split()]
	polarity = input()
	A_sorted = sorted(A)
	if len(A) == 1:
		results.append(0)
		continue
	if A == A_sorted:
		results.append(0)
		continue
	if 'S' not in polarity or 'N' not in polarity:
		results.append(-1)
		continue
	is_ordered = [A_sorted[i] == A[i] for i in range(len(A))]
	first_false = is_ordered.index(False)
	last_false = len(is_ordered) - 1 - is_ordered[::-1].index(False)
	if 'N' in polarity[:first_false + 1] and 'S' in polarity[last_false:] or ('S' in polarity[:first_false + 1] and 'N' in polarity[last_false:]):
		results.append(1)
	else:
		results.append(2)
for result in results:
	print(result)


T = int(input())
while T:
	T -= 1
	N = int(input())
	arr = list(map(int, input().split()))
	polar = input()
	sorted_arr = sorted(arr)
	if arr == sorted_arr:
		print(0)
		continue
	if polar[0] != polar[-1]:
		print(1)
		continue
	if polar.count('N') == len(polar) or polar.count('S') == len(polar):
		print(-1)
		continue
	start = float('inf')
	end = float('-inf')
	for i in range(N):
		if arr[i] != sorted_arr[i]:
			start = min(start, i)
			end = max(end, i)
	if polar[start] != polar[end]:
		print(1)
		continue
	else:
		flag = False
		for i in range(start):
			if polar[i] != polar[end]:
				flag = True
		for j in range(end + 1, N):
			if polar[j] != polar[start]:
				flag = True
		if flag:
			print(1)
		else:
			print(2)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	arr = []
	for j in a:
		arr.append(j)
	arr.sort()
	c = c1 = c2 = d = e = 0
	for j in range(n - 1):
		if a[j] > a[j + 1]:
			c = 1
			break
	if c == 0:
		print(0)
	else:
		for j in range(n):
			if s[j] == 'N':
				c1 = c1 + 1
			else:
				c2 = c2 + 1
		if c1 == 0 or c2 == 0:
			print(-1)
		else:
			for j in range(n - 1):
				if s[j] != s[n - 1]:
					p1 = j
					break
			for j in range(n - 1, 0, -1):
				if s[j] != s[0]:
					p2 = j
					break
			for j in range(p1):
				if a[j] != arr[j]:
					d = 1
					break
			for j in range(p2 + 1, n):
				if a[j] != arr[j]:
					e = 1
					break
			if d == 1 and e == 1:
				print(2)
			else:
				print(1)


import math
import os
import random
import re
import sys
from math import sqrt

class Solution_Max:

	def __init__(self, maxsize):
		self.maxsize = maxsize
		self.size = 0
		self.Heap = [0] * (self.maxsize + 1)
		self.Heap[0] = sys.maxsize
		self.FRONT = 1

	def parent(self, pos):
		return pos // 2

	def leftChild(self, pos):
		return 2 * pos

	def rightChild(self, pos):
		return 2 * pos + 1

	def isLeaf(self, pos):
		if pos >= self.size // 2 and pos <= self.size:
			return True
		return False

	def swap(self, fpos, spos):
		(self.Heap[fpos], self.Heap[spos]) = (self.Heap[spos], self.Heap[fpos])

	def maxHeapify(self, pos):
		if not self.isLeaf(pos):
			if self.Heap[pos] < self.Heap[self.leftChild(pos)] or self.Heap[pos] < self.Heap[self.rightChild(pos)]:
				if self.Heap[self.leftChild(pos)] > self.Heap[self.rightChild(pos)]:
					self.swap(pos, self.leftChild(pos))
					self.maxHeapify(self.leftChild(pos))
				else:
					self.swap(pos, self.rightChild(pos))
					self.maxHeapify(self.rightChild(pos))

	def insert(self, element):
		if self.size >= self.maxsize:
			return
		self.size += 1
		self.Heap[self.size] = element
		current = self.size
		while self.Heap[current] > self.Heap[self.parent(current)]:
			self.swap(current, self.parent(current))
			current = self.parent(current)

	def extractMax(self):
		popped = self.Heap[self.FRONT]
		self.Heap[self.FRONT] = self.Heap[self.size]
		self.size -= 1
		self.maxHeapify(self.FRONT)
		return popped

class Solution_Min:

	def __init__(self, maxsize):
		self.maxsize = maxsize
		self.size = 0
		self.Heap = [0] * (self.maxsize + 1)
		self.Heap[0] = -1 * sys.maxsize
		self.FRONT = 1

	def parent(self, pos):
		return pos // 2

	def leftChild(self, pos):
		return 2 * pos

	def rightChild(self, pos):
		return 2 * pos + 1

	def isLeaf(self, pos):
		return pos * 2 > self.size

	def swap(self, fpos, spos):
		(self.Heap[fpos], self.Heap[spos]) = (self.Heap[spos], self.Heap[fpos])

	def minHeapify(self, pos):
		if not self.isLeaf(pos):
			if self.Heap[pos] > self.Heap[self.leftChild(pos)] or self.Heap[pos] > self.Heap[self.rightChild(pos)]:
				if self.Heap[self.leftChild(pos)] < self.Heap[self.rightChild(pos)]:
					self.swap(pos, self.leftChild(pos))
					self.minHeapify(self.leftChild(pos))
				else:
					self.swap(pos, self.rightChild(pos))
					self.minHeapify(self.rightChild(pos))

	def insert(self, element):
		if self.size >= self.maxsize:
			return
		self.size += 1
		self.Heap[self.size] = element
		current = self.size
		while self.Heap[current] < self.Heap[self.parent(current)]:
			self.swap(current, self.parent(current))
			current = self.parent(current)

	def minHeap(self):
		for pos in range(self.size // 2, 0, -1):
			self.minHeapify(pos)

	def remove(self):
		popped = self.Heap[self.FRONT]
		self.Heap[self.FRONT] = self.Heap[self.size]
		self.size -= 1
		self.minHeapify(self.FRONT)
		return popped

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom

def isPowerOf2(x):
	return x and (not x & x - 1)

def power2(n):
	return len(str(bin(n & ~(n - 1))) - 1)

def sumn(n):
	return n * (n + 1) // 2

def sqsum(n):
	return n * (n + 1) * (2 * n + 1) // 6

def cusum(n):
	return sumn(n) ** 2

def dif(lista, listb):
	return len(set(lista + listb))

def prefixSum(arr):
	for i in range(1, len(arr)):
		arr[i] = arr[i] + arr[i - 1]
	return arr

def countSetBits(n):
	if n == 0:
		return 0
	else:
		return (n & 1) + countSetBits(n >> 1)

def Result(arr, s1):
	mx = 2147483647
	mn = -2147483648
	res1 = 1
	res2 = 2
	res3 = 0
	res4 = -1
	count = 0
	count1 = 0
	count3 = 0
	if arr == sorted(arr):
		print('0')
		return
	elif s1.count('N') == 0 or s1.count('S') == 0:
		print('-1')
		return
	n = len(arr)
	list1 = arr
	arr = sorted(arr)
	a = mx
	b = mn
	for i in range(0, n):
		if arr[i] != list1[i]:
			a = min(i, a)
			b = max(i, b)
	true1 = False
	true2 = False
	for i in range(0, a):
		if s1[i] != s1[b]:
			true1 = True
	for i in range(b, n):
		if s1[i] != s1[a]:
			true2 = True
	if s1[a] != s1[b] or (true1 or true2):
		print(res1)
		return
	else:
		print(res2)
		return
t = int(input())
for i in range(0, t):
	n = int(input())
	list1 = list(map(int, input().split()))
	s1 = input()
	Result(list1, s1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	s = input()
	if sorted(arr) == arr:
		print(0)
	elif s.count('N') == n or s.count('N') == 0:
		print(-1)
	else:
		a = sorted(arr)
		b = arr
		start = 2147483647
		last = -2147483647 - 1
		for i in range(n):
			if a[i] != b[i]:
				start = min([i, start])
				last = max([last, i])
		f1 = False
		f2 = False
		for i in range(start):
			if s[i] != s[last]:
				f1 = True
		for i in range(last, n):
			if s[i] != s[start]:
				f2 = True
		if s[start] != s[last] or f1 or f2:
			print(1)
		else:
			print(2)


def solve(a, p, s):
	if a == s:
		return 0
	elif p[0] != p[-1]:
		return 1
	elif ('N' in p) == False or ('S' in p) == False:
		return -1
	if p[0] == p[-1]:
		start = 2147483647
		last = -2147483648
		for i in range(n):
			if s[i] != a[i]:
				start = min(i, start)
				last = max(last, i)
		a1 = False
		a2 = False
		for i in range(start):
			if p[i] != p[start]:
				a1 = True
		for i in range(last, n):
			if p[i] != p[start]:
				a1 = True
		if p[start] != p[last] or a1 or a2:
			return 1
		else:
			return 2
T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	p = input()
	s = sorted(a)
	print(solve(a, p, s))


try:
	for test in range(int(input())):
		n = int(input())
		mapp = list(map(int, input().split()))
		sortedmapp = sorted(mapp)
		strt = input()
		if mapp == sortedmapp:
			print(0)
		else:
			fnnn = 0
			lst = n - 1
			for i in range(n):
				if mapp[i] != sortedmapp[i]:
					fnnn = i
					break
			for i in range(n - 1, -1, -1):
				if mapp[i] != sortedmapp[i]:
					la = i
					break
			zeus = True
			zeus = set()
			for i in range(fnnn + 1):
				zeus.add(strt[i])
			for i in range(n - 1, la - 1, -1):
				zeus.add(strt[i])
			if len(zeus) == 2:
				print(1)
			elif strt.count(strt[0]) == n:
				print(-1)
			else:
				print(2)
except EOFError:
	pass


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	d = a.copy()
	d.sort()
	flag = 1
	for i in range(n):
		if d[i] != a[i]:
			flag = 0
			break
	if flag == 1:
		print(0)
	else:
		countn = 0
		counts = 0
		for i in range(n):
			if s[i] == 'N':
				countn += 1
			else:
				counts += 1
		if countn == 0 or counts == 0:
			print(-1)
		elif s[0] != s[n - 1]:
			print(1)
		else:
			flag = 1
			for i in range(n - 1, -1, -1):
				if a[i] != d[i]:
					if s[i] == s[0]:
						flag = 0
					break
				elif s[i] != s[0]:
					break
			if flag == 1:
				print(1)
			else:
				flag = 1
				for i in range(n):
					if a[i] != d[i]:
						if s[i] == s[n - 1]:
							flag = 0
						break
					elif s[i] != s[0]:
						break
				if flag == 1:
					print(1)
				else:
					print(2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = input()
	c = sorted(a)
	d = 0
	e = f = 0
	if a != c:
		if 'N' not in b or 'S' not in b:
			print(-1)
			continue
		if b[0] != b[-1]:
			print(1)
			continue
		for i in range(n):
			if a[i] != c[i]:
				e = i
				break
		for i in range(n - 1, 0, -1):
			if a[i] != c[i]:
				f = i
				break
		if 'N' in b[:e + 1] and 'S' in b[f:] or ('S' in b[:e + 1] and 'N' in b[f:]):
			print(1)
		else:
			print(2)
	else:
		print(0)


t = int(input())
while t != 0:
	n = int(input())
	A = list(map(int, input().split()))
	s = input()
	B = sorted(A)
	k = set(s)
	if A == B:
		print(0)
		t -= 1
		continue
	if 'N' not in k or 'S' not in k:
		print(-1)
		t -= 1
		continue
	i = 0
	while i < n and A[i] == B[i]:
		i += 1
	j = n - 1
	while j >= 0 and A[j] == B[j]:
		j -= 1
	ok = 0
	for k in range(i + 1):
		if s[k] != s[j]:
			ok = 1
			break
	for k in range(n - 1, j - 1, -1):
		if s[k] != s[i]:
			ok = 1
			break
	if i < j and ok:
		print(1)
	else:
		print(2)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	s = input()
	arr2 = []
	for i in arr:
		arr2.append(i)
	arr.sort()
	if arr == arr2:
		print(0)
	elif 'S' not in s or 'N' not in s:
		print(-1)
	else:
		start = 99999999999999999
		end = -999999999999999
		for i in range(n):
			if arr[i] != arr2[i]:
				start = min(i, start)
				end = max(end, i)
		f1 = False
		f2 = False
		for i in range(start):
			if s[i] != s[end]:
				f1 = True
		for i in range(end, n):
			if s[i] != s[start]:
				f2 = True
		if s[start] != s[end] or f1 or f2:
			print(1)
		else:
			print(2)


def getCount():
	for k in range(num):
		if arr1[k] != sorted[k]:
			break
	pol = arr2[k]
	if pol == 'N':
		for l in range(num - 1, k, -1):
			if arr1[l] != sorted[l] and arr2[l] == 'N':
				break
			if (arr1[l] != sorted[l] or arr1[l] == sorted[l]) and arr2[l] == 'S':
				return 1
	elif pol == 'S':
		for l in range(num - 1, k, -1):
			if arr1[l] != sorted[l] and arr2[l] == 'S':
				break
			if (arr1[l] != sorted[l] or arr1[l] == sorted[l]) and arr2[l] == 'N':
				return 1
	pol2 = arr2[l]
	if pol2 == 'S':
		for g in range(k + 1):
			if arr2[g] == 'N':
				return 1
	else:
		for g in range(k + 1):
			if arr2[g] == 'S':
				return 1
	return 2
n = int(input())
for _ in range(n):
	num = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = input()
	sorted = []
	for i in arr1:
		sorted.append(i)
	sorted.sort()
	if sorted == arr1:
		print('0')
	elif 'S' not in arr2 or 'N' not in arr2:
		print('-1')
	elif arr2[0] == 'S' and arr2[len(arr2) - 1] == 'N' or (arr2[0] == 'N' and arr2[len(arr2) - 1] == 'S'):
		print('1')
	else:
		print(getCount())


import copy
t = int(input())
for y in range(t):
	n = int(input())
	org = list(map(int, input().split()))
	pol = list(input())
	srt = copy.deepcopy(org)
	srt.sort()
	if srt == org:
		print(0)
		continue
	if 'N' not in pol or 'S' not in pol:
		print(-1)
		continue
	f = 0
	r = n - 1
	for y in range(f, r + 1):
		if org[y] == srt[y]:
			f += 1
		else:
			break
	for y in range(r, f - 1, -1):
		if org[y] == srt[y]:
			r -= 1
		else:
			break
	c = pol[:f]
	v = pol[r + 1:]
	m = pol[f:r + 1]
	a = pol[f]
	b = pol[r]
	if a != b:
		print(1)
	elif a == 'N' and 'S' in v:
		print(1)
	elif a == 'S' and 'N' in v:
		print(1)
	elif b == 'N' and 'S' in c:
		print(1)
	elif b == 'S' and 'N' in c:
		print(1)
	elif 'N' in c and 'S' in v:
		print(1)
	elif 'S' in c and 'N' in v:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	s = input()
	arr1 = sorted(arr)
	if arr == arr1:
		print(0)
		continue
	if s.count('N') in [n, 0]:
		print(-1)
		continue
	(pre, post) = (n + 1, -1)
	for i in range(n):
		if arr[i] != arr1[i]:
			pre = min(i, pre)
			post = max(i, post)
	(a, b) = (False, False)
	for i in range(pre):
		if s[i] != s[post]:
			a = True
	for i in range(post, n):
		if s[i] != s[pre]:
			b = True
	if s[pre] != s[post] or a or b:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = input().strip()
	if a == sorted(a) or n == 1:
		print(0)
		continue
	if s.count('N') == n or s.count('S') == n:
		print(-1)
		continue
	if s[0] == 'N' and s[-1] == 'S' or (s[0] == 'S' and s[-1] == 'N'):
		print(1)
	else:
		b = sorted(a)
		start = s[0]
		(A, B) = (0, 0)
		for i in range(n):
			if s[i] != start:
				A = i
				break
		for i in range(n - 1, -1, -1):
			if s[i] != start:
				B = i
				break
		if b[:A] == a[:A] or b[B + 1:] == a[B + 1:]:
			print(1)
		else:
			print(2)


for t in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split(' ')))
	dirc = input()
	if lst == sorted(lst):
		print(0)
	elif dirc[0] != dirc[n - 1]:
		print(1)
	elif 'N' in dirc and 'S' in dirc:
		i = n - 1
		while dirc[0] == dirc[i]:
			i -= 1
		else:
			if sorted(lst[:i + 1]) + lst[i + 1:] == sorted(lst):
				print(1)
			else:
				i = 0
				while dirc[n - 1] == dirc[i]:
					i += 1
				else:
					if lst[:i] + sorted(lst[i:]) == sorted(lst):
						print(1)
					else:
						print(2)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = input().strip()
	if a == sorted(a) or n == 1:
		print(0)
		continue
	if s.count('N') == n or s.count('S') == n:
		print(-1)
		continue
	if s[0] == 'N' and s[-1] == 'S' or (s[0] == 'S' and s[-1] == 'N'):
		print(1)
	else:
		for i in range(n - 1, -1, -1):
			if s[0] != s[i]:
				y = i
				break
		for i in range(n):
			if s[-1] != s[i]:
				x = i
				break
		a1 = a[:x] + sorted(a[x:])
		a2 = sorted(a[:y + 1]) + a[y + 1:]
		b = sorted(a)
		if b == a1 or b == a2:
			print(1)
		else:
			print(2)