We define a function f on a binary string S of length N as follows:

f(S) = \sum_{i = 1}^{N - 1} |S_{i+1} - S_{i}|.

JJ and Uttu have a binary string S of length N and they decide to play a game using it. The rules of the game are as follows:

JJ starts the game with players making moves in alternate turns thereafter.
In one move, a player can pick L, R such that 1 ≤ L ≤ R ≤ N and flip all the characters in S_{L \dots R} (Flipping a character means changing 0 to 1 or 1 to 0).
A player can only make a move if that move increases the value of f(S).
The player who can not make any further moves loses.

Which player (out of JJ and Uttu) will win the game, assuming that both the players play optimally?

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

- The first line contains T - the number of test cases. Then the test cases follow.
- The first line of each test case contains N -  the length of the binary string S.
- The second line of each test case contains a binary string S.

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

For each test case, output which player wins the game, whether it's JJ and Uttu will win the game.

You may print each character of the string in uppercase or lowercase (for example, the strings JJ, Jj and jj will all be treated as identical).

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 2000$

----- Sample Input 1 ------ 
3
5
10011
2
00
5
10101
----- Sample Output 1 ------ 
JJ
JJ
Uttu
----- explanation 1 ------ 
- Test case $1$: JJ can perform the following move: $10\underline{01}1 \rightarrow 10101$. Now Uttu cannot perform any moves and thereby loses.
- Test case $2$: JJ can perform the following move: $0\underline{0} \rightarrow 01$. Now Uttu cannot perform any moves and thereby loses.
- Test case $3$: JJ cannot perform any starting moves, thereby he loses.

Difficulty: HARD
Tags: String algorithms

Data structures

Game theory
Skill types: Data structures

Starter code:

Solutions:
from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(10 ** 7)
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
from functools import lru_cache

@lru_cache(None)
def fn(cnt):
	if cnt == 0:
		return False
	ans = False
	if cnt >= 1:
		if fn(cnt - 1) == False:
			ans = True
	if not ans and cnt >= 2:
		if fn(cnt - 2) == False:
			ans = True
	return ans
for _ in range(nmbr()):
	n = nmbr()
	s = input()
	cnt = sum((int(ch1 == ch2) for (ch1, ch2) in zip(s, s[1:])))
	if fn(cnt):
		print('JJ')
	else:
		print('Uttu')


for i in range(int(input())):
	n = int(input())
	s = input()
	a = [int(x) for x in s]
	l = []
	for i in range(1, n):
		l.append(abs(a[i] - a[i - 1]))
	z = 0
	for i in range(n - 1):
		if l[i] == 0:
			z += 1
	if z % 3 == 0:
		print('Uttu')
	else:
		print('JJ')


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			ans += 1
	if ans % 3 == 0:
		print('Uttu')
	else:
		print('JJ')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	c = 0
	for j in range(n - 1):
		if s[j] == s[j + 1]:
			c += 1
	print('JJ' if c % 3 else 'Uttu')


t = int(input())
for _ in range(t):
	n = int(input())
	seq = input()
	c = 0
	for i in range(n - 1):
		if seq[i] == seq[i + 1]:
			c += 1
	print('JJ' if c % 3 else 'Uttu')


for _ in range(int(input())):
	n = int(input())
	bs = input()
	cnt = 0
	for i in range(1, n):
		if bs[i] == bs[i - 1]:
			cnt += 1
	if cnt % 3 == 0:
		print('Uttu')
	else:
		print('JJ')


t = int(input())
for i in range(t):
	n = int(input())
	l = input()
	c = 0
	for k in range(1, n):
		if l[k] == l[k - 1]:
			c += 1
	if c % 3 != 0:
		print('JJ')
	else:
		print('Uttu')


def cc(n, s):
	cnt = 0
	for i in range(1, n):
		if int(s[i]) - int(s[i - 1]) == 0:
			cnt += 1
	if cnt % 3 == 0:
		print('Uttu')
	else:
		print('JJ')
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	cc(n, s)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip()))
	d = []
	for i in range(1, n):
		d.append(abs(l[i] - l[i - 1]))
	rem = n - 1 - sum(d)
	if rem % 3 == 0:
		print('Uttu')
	else:
		print('JJ')


for i in range(int(input())):
	n = int(input())
	s = str(input())
	a = 0
	for j in range(n - 1):
		if s[j] == s[j + 1]:
			a += 1
	if a % 3 == 0:
		print('Uttu')
	else:
		print('JJ')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	a = 0
	b = 0
	one = 1
	prev = -2
	first = -1
	for i in range(n):
		if one:
			if s[i] == '1':
				one = 0
			else:
				if i - prev != 1:
					if first == -1:
						first = i
					a = a + 1
				prev = i
				one = 0
		elif s[i] == '0':
			one = 1
		else:
			if i - prev != 1:
				if first == -1:
					first = i
				a = a + 1
			prev = i
			one = 1
	if first == 0:
		if prev == n - 1:
			b = a - 1
		else:
			b = a
	elif prev == n - 1:
		b = a
	else:
		b = a + 1
	dp = [[0, 0] for i in range(min(a, b) + 1)]
	dp[0][0] = -1
	dp[0][1] = 0
	for i in range(1, min(a, b) + 1):
		dp[i][0] = not (dp[i - 1][0] and dp[i - 1][1])
		dp[i][1] = not (dp[i][0] and dp[i - 1][1])
	if dp[min(a, b)][max(a, b) - min(a, b)]:
		print('JJ')
	else:
		print('Uttu')


for _ in range(int(input())):
	n = int(input())
	s = input()
	change = n - 1
	for i in range(n - 1):
		if s[i + 1] != s[i]:
			change -= 1
	print('JJ' if change % 3 else 'Uttu')


T = int(input())
for t in range(T):
	n = int(input())
	s = list(map(int, list(input())))
	f = 0
	for i in range(n - 1):
		f += abs(s[i] - s[i + 1])
	n -= 1
	if (n - f) % 3:
		print('JJ')
	else:
		print('Uttu')


for _ in range(int(input())):
	n = int(input())
	s = input()
	r = s.count('01') + s.count('10')
	r = n - 1 - r
	if r % 3 == 0:
		print('Uttu')
	else:
		print('JJ')


def solve():
	n = int(input())
	s = input()
	c = 0
	for i in range(1, n):
		if s[i] == s[i - 1]:
			c += 1
	if c % 3 == 0:
		print('Uttu')
	else:
		print('JJ')
T = int(input())
for i in range(T):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	d = []
	for j in range(n - 1):
		if a[j] == a[j + 1]:
			d.append(0)
		else:
			d.append(1)
	c = d.count(0)
	if c % 3 == 0:
		print('Uttu')
	else:
		print('JJ')


t = int(input())
for _ in range(t):
	n = int(input())
	st = input()
	s = 0
	for i in range(n - 1):
		s += abs(ord(st[i + 1]) - ord(st[i]))
	rem = n - 1 - s
	if rem % 3 == 0:
		print('Uttu')
	else:
		print('JJ')


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = []
	for i in range(n - 1):
		l.append(abs(int(s[i + 1]) - int(s[i])))
	x = l.count(0)
	if x % 3 == 0:
		print('Uttu')
	else:
		print('JJ')


for _ in range(int(input())):
	n = int(input())
	b = input()
	L = b[0]
	for i in range(1, n):
		if b[i] != L[-1]:
			L += b[i]
	t = n - len(L)
	if t % 3 == 0:
		print('Uttu')
	else:
		print('JJ')


t = int(input())
for _ in range(t):
	n = int(input())
	S = input()
	dif = 0
	for i in range(1, len(S)):
		dif += abs(int(S[i]) - int(S[i - 1]))
	dif = n - 1 - dif
	if dif % 3 == 0:
		print('Uttu')
	else:
		print('JJ')


for _ in range(int(input())):
	n = int(input())
	s = input()
	cnt = sum((1 for i in range(n - 1) if s[i] == s[i + 1]))
	print('Uttu' if not cnt % 3 else 'JJ')


def main():
	n = int(input())
	bich = input()
	LOL = bich[0]
	for i in range(1, n):
		if bich[i] != LOL[-1]:
			LOL += bich[i]
	fft = n - len(LOL)
	if fft % 3 == 0:
		return 'Uttu'
	return 'JJ'
for _ in range(int(input())):
	print(main())


def fS(bins):
	tot = 0
	for i in range(0, len(bins) - 2):
		tot += abs(int(bins[i + 1]) - int(bins[i]))
	return tot

def isStop(bins):
	for i in range(0, n - 1):
		if bins[i] == bins[i + 1]:
			return True
	return False
for _ in range(int(input())):
	n = int(input())
	bin = input()
	mcnt0 = 0
	mcnt1 = 0
	cnt0 = 0
	cnt1 = 0
	if bin[0] == '0':
		cnt0 += 1
	else:
		cnt1 += 1
	val = 0
	c = bin[0]
	for i in range(1, len(bin)):
		val += abs(int(bin[i]) - int(bin[i - 1]))
		if bin[i] == c:
			if c == '0':
				cnt0 += 1
			else:
				cnt1 += 1
		else:
			mcnt1 = max(mcnt1, cnt1)
			mcnt0 = max(mcnt0, cnt0)
			c = bin[i]
			cnt0 = 0
			cnt1 = 0
			if c == '0':
				cnt0 += 1
			else:
				cnt1 += 1
	mcnt1 = max(mcnt1, cnt1)
	mcnt0 = max(mcnt0, cnt0)
	val = n - 1 - val
	if val % 3 == 0:
		print('Uttu')
	else:
		print('JJ')


def f(count, t):
	if count == 0:
		return 0
	elif L[count][t] != -1:
		return L[count][t]
	x = 0
	if count >= 1:
		x = x or not f(count - 1, not t)
	if count >= 2:
		x = x or not f(count - 2, not t)
	L[count][t] = x
	return x
T = int(input())
for tc in range(T):
	n = int(input())
	s = input()
	count = 0
	for i in range(n - 1):
		if s[i + 1] == s[i]:
			count += 1
	L = [[-1, -1] for i in range(n)]
	if f(count, 0) == 1:
		print('JJ')
	else:
		print('Uttu')


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
sys.setrecursionlimit(100000)

def solve():

	def helper(a, b):
		if not a:
			return False
		if dp[a][b] != -1:
			return dp[a][b]
		cur = not helper(a - 1, (b + 1) % 2)
		if a >= 2:
			cur = cur or not helper(a - 2, (b + 1) % 2)
		dp[a][b] = cur
		return cur
	n = inp()
	s = st()
	dp = [[-1, -1] for i in range(n + 1)]
	val = 0
	for i in range(1, n):
		val += s[i] == s[i - 1]
	pr('JJ' if helper(val, 0) else 'Uttu')
for _ in range(inp()):
	solve()


import sys
sys.setrecursionlimit(10 ** 6)

def fun(d, i, j):
	if i <= 0:
		return False
	if d[i][j] != -1:
		return d[i][j]
	ans = False
	if i >= 2:
		ans |= not fun(d, i - 2, not j)
	if i >= 1:
		ans |= not fun(d, i - 1, not j)
	d[i][j] = ans
	return d[i][j]
for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	d = [[-1, -1] for i in range(n + 5)]
	for i in range(n - 1):
		if s[i + 1] == s[i]:
			ans += 1
	x = fun(d, ans, 0)
	if x == True:
		print('JJ')
	else:
		print('Uttu')


def solve(val, flag, dp):
	if val == 0:
		return False
	if dp[val][flag] != -1:
		return dp[val][flag]
	res = False
	if val >= 1:
		res = res or not solve(val - 1, not flag, dp)
	if val >= 2:
		res = res or not solve(val - 2, not flag, dp)
	dp[val][flag] = res
	return dp[val][flag]
for t in range(int(input())):
	n = int(input())
	s = input()
	dp = [[-1 for i in range(2)] for j in range(n + 1)]
	count = 0
	for i in range(n - 1):
		count += s[i] == s[i + 1]
	if solve(count, 0, dp):
		print('JJ')
	else:
		print('Uttu')


def fn(v, p):
	if v == 0:
		return False
	if d[v][p] != -1:
		return d[v][p]
	ans = False
	if v >= 1:
		ans = ans or not fn(v - 1, not p)
	if v >= 2:
		ans = ans or not fn(v - 2, not p)
	d[v][p] = ans
	return ans
for i in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	d = [[-1 for i in range(2)] for i in range(n)]
	for i in range(n):
		d[i][0] = d[i][1] = -1
	for i in range(n - 1):
		ans += s[i] == s[i + 1]
	if fn(ans, 0):
		print('JJ')
	else:
		print('Uttu')


t = int(input())
for _ in range(t):
	n = int(input())
	st = input().strip()
	s = 0
	for j in range(1, n):
		if st[j] != st[j - 1]:
			s += 1
	if (n - 1 - s) % 3 == 0:
		print('Uttu')
	else:
		print('JJ')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input().strip()
	curr_sum = 0
	prev = s[0]
	for i in s[1:]:
		if i != prev:
			curr_sum += 1
		prev = i
	if (n - 1 - curr_sum) % 3 == 0:
		print('Uttu')
	else:
		print('JJ')


T = int(input())
for i in range(T):
	count = 0
	N = int(input())
	input_string = input()
	for i in range(N - 1):
		if input_string[i] + input_string[i + 1] == '00' or input_string[i] + input_string[i + 1] == '11':
			count = count + 1
	if count % 3 == 0:
		print('Uttu')
	else:
		print('JJ')


import math

def swaps(data):
	result = 0
	for i in range(1, len(data)):
		if data[i] != data[i - 1]:
			result += 1
	return result

def test(data):
	max_swaps = len(data) - 1
	cur_swaps = swaps(data)
	available = max_swaps - cur_swaps
	return available
for _ in range(int(input())):
	_ = input()
	data = input()
	moves = test(data)
	if moves % 3 == 0:
		print('Uttu')
	else:
		print('JJ')


def main():
	n = int(input())
	s = input()
	aux = s[0]
	for i in range(1, n):
		if s[i] != aux[-1]:
			aux += s[i]
	final = n - len(aux)
	if final % 3 == 0:
		return 'Uttu'
	return 'JJ'
for _ in range(int(input())):
	print(main())


for _ in range(int(input())):
	N = int(input())
	B = list(map(int, input()))
	f = sum([int(L != R) for (L, R) in zip(B[:-1], B[1:])])
	pts_to_go = N - 1 - f
	print({0: 'Uttu', 1: 'JJ', 2: 'JJ'}[pts_to_go % 3])


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	N = int(input())
	A = input().strip()
	count = 0
	for i in range(1, len(A)):
		if A[i] == A[i - 1]:
			count += 1
	print('Uttu' if count % 3 == 0 else 'JJ')


T = int(input())
for i in range(T):
	N = int(input())
	S = list(str(input()))
	flips = 0
	cur = S[0]
	for theta in range(1, N):
		if S[theta] != cur:
			flips += 1
		cur = S[theta]
	potential = N - 1 - flips
	if potential % 3 == 0:
		print('Uttu')
	else:
		print('JJ')


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		self.merge_func = merge_func
		self.lg = [0] * (N + 1)
		for i in range(2, N + 1):
			self.lg[i] = self.lg[i >> 1] + 1
		self.pow_2 = [pow(2, i) for i in range(20)]
		self.table = [None] * (self.lg[N] + 1)
		st0 = self.table[0] = [a for a in A]
		b = 1
		for i in range(self.lg[N]):
			st0 = self.table[i + 1] = [self.merge_func(u, v) for (u, v) in zip(st0, st0[b:])]
			b <<= 1

	def query(self, s, t):
		b = t - s + 1
		m = self.lg[b]
		return self.merge_func(self.table[m][s], self.table[m][t - self.pow_2[m] + 1])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

class slope_trick:

	def __init__(self):
		self.L = [10 ** 17]
		self.R = [10 ** 17]
		self.min_f = 0
		self.x_left = 0
		self.x_right = 0

	def add_right(self, a):
		a -= self.x_left
		l0 = -self.L[0]
		self.min_f = self.min_f + max(0, l0 - a)
		if l0 <= a:
			a += self.x_left
			a -= self.x_right
			heappush(self.R, a)
		else:
			heappush(self.L, -a)
			a = -heappop(self.L)
			a += self.x_left
			a -= self.x_right
			heappush(self.R, a)

	def add_left(self, a):
		a -= self.x_right
		r0 = self.R[0]
		self.min_f = self.min_f + max(0, a - r0)
		if a <= r0:
			a += self.x_right
			a -= self.x_left
			heappush(self.L, -a)
		else:
			heappush(self.R, a)
			a = heappop(self.R)
			a += self.x_right
			a -= self.x_left
			heappush(self.L, -a)

	def add_abs(self, a):
		self.add_left(a)
		self.add_right(a)

	def change_min_slide(self, a, b):
		self.x_left += a
		self.x_right += b

	def get_val(self, x):
		L = [-l + self.x_left for l in self.L]
		L.sort()
		R = [r + self.x_right for r in self.R]
		R.sort()
		res = self.min_f
		if 0 < L[-1]:
			L = L[::-1]
			n = len(L)
			for i in range(n):
				c0 = L[i]
				c1 = L[i + 1]
				if c1 <= x <= c0:
					res += (i + 1) * (c0 - x)
					break
				else:
					res += (i + 1) * (c0 - c1)
			return res
		elif L[-1] <= x <= R[0]:
			return res
		else:
			n = len(R)
			for i in range(n):
				c0 = R[i]
				c1 = R[i + 1]
				if c0 <= x <= c1:
					res += (i + 1) * (x - c0)
					break
				else:
					res += (i + 1) * (c1 - c0)
			return res

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.size = n
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			k >>= 1
			self.tree[k] = self.segfunc(self.tree[2 * k], self.tree[2 * k + 1])

	def query(self, l, r):
		if r == self.size:
			r = self.num
		res = self.ide_ele
		l += self.num
		r += self.num
		right = []
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				right.append(self.tree[r - 1])
			l >>= 1
			r >>= 1
		for e in right[::-1]:
			res = self.segfunc(res, e)
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
ori = '01' * 1000
for _ in range(int(input())):
	N = int(input())
	S = input()
	A = [S[i] == ori[i] for i in range(N)]
	k = 0
	s = A[0]
	for i in range(1, N):
		if s == A[i]:
			continue
		else:
			k += 1
			s = A[i]
	k += 1
	if k % 3 == 1:
		print('Uttu')
	else:
		print('JJ')


for i in range(int(input())):
	N = int(input())
	s = str(input())
	count = 0
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			count = count + 1
	if count % 3 == 0:
		print('Uttu')
	else:
		print('JJ')