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

A string is called a *Palpal string* if it can be divided into contiguous substrings such that:
Each character of the whole string belongs to exactly one substring.
Each of these substrings is a palindrome with length greater than $1$.

For example, "abbbaddzcz" is a Palpal string, since it can be divided into "abbba", "dd" and "zcz".

You are given a string $s$. You may rearrange the characters of this string in any way you choose. Find out if it is possible to rearrange them in such a way that you obtain a Palpal string.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains a single string $s$.

------  Output ------
For each test case, print a single line containing the string "YES" if the characters of $s$ can be rearranged to form a Palpal string or "NO" if it is impossible (without quotes).

You may print each character of each string in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

------  Constraints ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ |s| ≤ 100$
$s$ contains only lowercase English letters
the sum of $|s|$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (100 points): original constraints

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

acbbbadzdz

abcd

xyxyxy
----- Sample Output 1 ------ 
YES

NO

YES
----- explanation 1 ------ 
Example case 1: The string "acbbbadzdz" can be rearranged to "abbbaddzcz", which is the Palpal string mentioned above.

Example case 2: It can be shown that "abcd" cannot be rearranged to form a Palpal string.

Example case 3: The string "xyxyxy" is already a Palpal string, since it can divided into "xyx" and "yxy".

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Constructive algorithms


Solutions:
n = int(input())
for i in range(n):
	val = input()
	count = {}
	for i in val:
		if i not in count:
			count[i] = 1
		else:
			count[i] += 1
	odds = 0
	for i in count:
		if count[i] % 2 == 1:
			odds += 1
	if (len(val) - odds) // 2 >= odds and len(val) != odds:
		print('YES')
	else:
		print('NO')


from bisect import bisect_left, bisect_right
import math
from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

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 a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

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
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	s = ip()
	d = {}
	for i in s:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	e = 0
	o = 0
	one = 0
	for (k, v) in d.items():
		if v == 1:
			one += 1
		elif v % 2 == 0:
			e += v // 2
		elif v % 2 != 0:
			e += v // 2 - 1
	if one <= e:
		print('YES')
	else:
		print('NO')


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

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

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

def ip():
	return input()
for tastcas in range(int(input())):
	s = ip()
	dic = {}
	odds = 0
	pairs = 0
	for i in s:
		dic[i] = dic.get(i, 0) + 1
	for (k, v) in dic.items():
		pair = v // 2
		odd = v - pair * 2
		pairs += pair
		odds += odd
	if odds <= pairs:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	s = input()
	frq = [0] * 26
	for i in range(len(s)):
		frq[ord(s[i]) - 97] += 1
	odd = 0
	for f in range(26):
		if frq[f] % 2 != 0:
			odd += 1
	pairs = (len(s) - odd) // 2
	if pairs < odd:
		print('NO')
	else:
		print('YES')
	t -= 1


from sys import stdin, stdout
from collections import Counter
input = stdin.readline
t = int(input().strip())
for _ in range(t):
	s = input().strip()
	d = Counter(s)
	(odd, pair) = (0, 0)
	for key in d:
		value = d[key]
		if value % 2 != 0:
			odd += 1
		pair += value // 2
	if odd > pair:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	hash = {}
	for i in s:
		if i not in hash:
			hash[i] = 1
		else:
			hash[i] += 1
	even = 0
	odd = 0
	one = 0
	for (k, v) in hash.items():
		if v == 1:
			one += 1
		elif v % 2 == 0:
			even += v // 2
		elif v % 2 != 0:
			even += v // 2 - 1
	if one <= even:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	s = input()
	d = {}
	ans = 'YES'
	for j in s:
		if j not in d:
			d[j] = 1
		else:
			d[j] += 1
	o = 0
	e = 0
	for k in d.values():
		if k == 1:
			o += 1
		elif k % 2 == 0:
			e += k // 2
		else:
			e += k // 2 - 1
	if o > e:
		ans = 'NO'
	print(ans)


def solve(s):
	d = {}
	ans = 'YES'
	for i in s:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	(one, even) = (0, 0)
	for v in d.values():
		if v == 1:
			one += 1
		elif v % 2 == 0:
			even += v // 2
		else:
			even += v // 2 - 1
	if one > even:
		ans = 'NO'
	print(ans)
for _ in range(int(input())):
	s = input()
	solve(s)


t = int(input())
for i in range(t):
	a = input()
	p = 0
	up = 0
	for x in a:
		p += a.count(x) // 2
		up += a.count(x) % 2
		a = a.replace(x, '')
	if p >= up:
		print('YES')
	else:
		print('NO')


try:
	t = int(input())
	i = 1
	while i <= t:
		i = i + 1
		s = input()
		uniq = []
		uniq_frq = []
		dick = {}
		for x in s:
			if x not in dick.keys():
				dick[x] = 1
			else:
				dick[x] = dick[x] + 1
		uniq_frq = list(dick.values())
		count1 = 0
		count2 = 0
		o = 0
		for p in range(0, len(uniq_frq)):
			if int(uniq_frq[p]) % 2 == 0:
				count2 = count2 + int(uniq_frq[p]) // 2
			elif int(uniq_frq[p]) % 2 != 0:
				o = int(uniq_frq[p] // 2) - 1
				if o < 0:
					o = 0
				count2 = count2 + o
		for u in range(0, len(uniq_frq)):
			if uniq_frq[u] == 1:
				count1 = count1 + 1
		if count2 >= count1:
			print('YES')
		else:
			print('NO')
except:
	pass


try:
	t = int(input())
	i = 1
	while i <= t:
		i = i + 1
		s = []
		a = input()
		for z in a:
			s.append(z)
		uni = []
		for x in range(0, len(s)):
			if s[x] not in uni:
				uni.append(s[x])
		count1 = 0
		count2 = 0
		frq = []
		for u in range(0, len(uni)):
			count = 0
			for v in range(0, len(s)):
				if uni[u] == s[v]:
					count = count + 1
			frq.append(count)
		for k in range(0, len(frq)):
			if frq[k] == 1:
				count1 = count1 + 1
			elif frq[k] % 2 == 0:
				count2 = count2 + frq[k] // 2
			elif frq[k] % 2 != 0:
				count2 = count2 + (frq[k] // 2 - 1)
		if len(s) == 1:
			print('NO')
		elif count1 > count2:
			print('NO')
		else:
			print('YES')
except:
	pass


try:
	for t in range(int(input())):
		s = str(input())
		dic = {}
		for i in s:
			if i not in dic:
				dic[i] = 0
			dic[i] += 1
		single = 0
		double = 0
		for i in dic.keys():
			if dic.get(i) == 1:
				single += 1
			if dic.get(i) >= 2 and dic.get(i) % 2 == 0:
				double += dic.get(i) / 2
			elif dic.get(i) >= 2 and dic.get(i) % 2 != 0:
				double += dic.get(i) // 2 - 1
		if single <= double:
			print('YES')
		else:
			print('NO')
except:
	pass


from collections import Counter
for _ in range(int(input())):
	ls = list(map(str, input().split()))
	lss = list(ls[0])
	check = Counter(sorted(lss))
	hmm = [cnt for (word, cnt) in check.most_common(len(check))]
	single = 0
	pair = 0
	for item in hmm:
		if item == 1:
			single += 1
		if item % 2 == 0:
			pair += item // 2
		if item % 2 != 0 and item > 3:
			pair += (item - 3) // 2
	print('YES' if single <= pair else 'NO')


n = int(input())
for i in range(n):
	cntodd = 0
	e = 0
	pal = input()
	s = set(pal)
	for i in s:
		if pal.count(i) % 2 != 0:
			cntodd += 1
			e += pal.count(i) - 1
		else:
			e += pal.count(i)
	if e // 2 >= cntodd:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	s = input()
	odd = 0
	even = 0
	for i in range(97, 123):
		x = s.count(chr(i))
		even = even + x // 2
		odd = odd + x % 2
	if odd > even:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	freq = [0] * 26
	for i in s:
		freq[ord(i) - 97] += 1
	(single, couple) = (0, 0)
	for j in freq:
		single += j // 2
		couple += j % 2
	if single >= couple:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	s = input()
	a = [0] * 26
	for i in s:
		a[ord(i) - 97] += 1
	e = 0
	o = 0
	for j in a:
		e += j // 2
		o += j % 2
	if e >= o:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	arr = [0] * 26
	for ch in s:
		arr[ord(ch) - 97] += 1
	(even, odd) = (0, 0)
	for num in arr:
		even += num // 2
		odd += num % 2
	if even >= odd:
		print('YES')
	else:
		print('NO')


from collections import Counter
for _ in range(int(input())):
	s = list(input().strip())
	dic = Counter(s)
	(e, f) = (0, 0)
	for v in dic.values():
		e += v // 2
		f += v % 2
	if f > e:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	(d, a, b) = ({}, 0, 0)
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for i in d:
		a = a + d[i] % 2
		b = b + d[i] // 2
	if a <= b:
		print('YES')
	else:
		print('NO')


for _ in range(int(input().strip())):
	s = input().strip()
	alpha = 'qwertyuiopasdfghjklmnbvczx'
	e = 0
	o = 0
	for i in alpha:
		x = s.count(i)
		if x % 2 == 0:
			e += x // 2
		else:
			e += (x - 1) // 2
			o += 1
	if e >= o:
		print('YES')
	else:
		print('NO')


import sys
for _ in range(int(sys.stdin.readline().strip())):
	s = sys.stdin.readline().strip()
	d = dict.fromkeys(s, 0)
	(single, couple) = (0, 0)
	for i in s:
		d[i] += 1
	for i in d:
		if d[i] == 1:
			single += 1
		elif d[i] % 2 == 0:
			couple += d[i] // 2
		elif d[i] > 3 and d[i] % 2 == 1:
			couple += (d[i] - 3) // 2
	if couple >= single:
		print('YES')
	else:
		print('NO')


import sys
for _ in range(int(sys.stdin.readline().strip())):
	s = sys.stdin.readline().strip()
	d = dict.fromkeys(s, 0)
	for i in s:
		d[i] += 1
	lst = list(d.values())
	if len(s) == len(set(s)):
		print('NO')
	else:
		even = 0
		odd = 0
		for i in lst:
			if i % 2 != 0:
				odd += 1
			even += i // 2
		if odd <= even:
			print('YES')
		else:
			print('NO')


from collections import Counter
t = int(input())
ans = []
for _ in range(t):
	s = input()
	d = Counter(s)
	(one, two) = (0, 0)
	for i in d:
		one += d[i] % 2
		two += d[i] // 2
	if one <= two:
		ans.append('YES')
	else:
		ans.append('NO')
for _ in ans:
	print(_)


from collections import defaultdict
for i in range(int(input())):
	s = input()
	dis = defaultdict(int)
	for i in s:
		dis[i] += 1
	od = 0
	for (k, v) in dis.items():
		if v % 2 != 0:
			od += 1
	x = (len(s) - od) / 2
	if od <= x:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	ss = input()
	hp = {}
	for i in ss:
		if i in hp:
			hp[i] += 1
		else:
			hp[i] = 1
	even = 0
	odd = 0
	for i in hp:
		even += hp[i] // 2
		if hp[i] % 2:
			odd += 1
	if odd <= even:
		print('YES')
	else:
		print('NO')


from collections import Counter
for _ in range(int(input())):
	s = input()
	a = Counter(s)
	(l, m, n) = (0, 0, 0)
	for i in a:
		l += a[i] % 2
		m += a[i] // 2
	if m >= l:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	s = input()
	s = sorted(s)
	x = len(s)
	l = []
	i = 0
	while i < x:
		c = 1
		j = i + 1
		while j < x:
			if s[i] != s[j]:
				break
			c += 1
			j += 1
		i = j
		l.append(c)
	even = ones = 0
	for i in range(len(l)):
		if l[i] == 1:
			ones += 1
		if l[i] % 2 == 0:
			even += l[i]
		if l[i] != 1 and l[i] >= 3 and (l[i] % 2 != 0):
			even += l[i] - 1
			ones += 1
	finall = even / 2
	if ones <= finall:
		print('YES')
	else:
		print('NO')


import sys
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]
from collections import Counter
for _ in range(RI()):
	inps = Counter(input())
	single = 0
	double = 0
	for k in inps.keys():
		(d, s) = divmod(inps[k], 2)
		double += d
		single += s
	print('YES' if single <= double else 'NO')


T = int(input())
for i in range(T):
	s = input()
	mp = {}
	for i in s:
		mp.setdefault(i, 0)
		mp[i] += 1
	od = 0
	for (k, v) in mp.items():
		if v % 2 != 0:
			od += 1
	x = (len(s) - od) / 2
	if od <= x:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	s = input()
	se = set(s)
	l = list(se)
	odcount = 0
	evec = 0
	for i in l:
		c = s.count(i)
		evec = evec + c // 2
		odcount = odcount + c % 2
	if evec >= odcount:
		print('YES')
	else:
		print('NO')
	t = t - 1


t = int(input())
for i in range(0, t):
	s = input()
	d = {}
	for j in range(0, len(s)):
		if d.get(s[j]) == None:
			d[s[j]] = s.count(s[j])
	k = list(d.values())
	even = 0
	odd = 0
	for z in range(0, len(k)):
		if k[z] % 2 == 0:
			even += k[z] // 2
		elif k[z] == 1:
			odd += 1
		elif k[z] > 3:
			re = k[z] - 3
			even += re // 2
	if even >= odd:
		print('YES')
	else:
		print('NO')


try:
	for _ in range(int(input())):
		li = [i for i in input()]
		li.sort()
		count = 0
		k = len(li)
		n = 0
		for i in range(k - 1):
			if li[i] == li[i + 1]:
				count += 1
				if n == 1:
					n -= 1
					count -= 1
					continue
				n += 1
				continue
			if n == 1:
				n -= 1
		if count >= k - 2 * count:
			print('YES')
		else:
			print('NO')
except:
	pass


for _ in range(int(input())):
	a = [0] * 26
	s = input()
	for i in s:
		a[ord(i) - 97] += 1
	(odd, even) = (0, 0)
	for i in a:
		if i % 2 == 0:
			even += i
		else:
			even += i - 1
			odd += 1
	even //= 2
	if odd <= even:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	s = input()
	dict1 = {}
	odd = 0
	even = 0
	for j in s:
		if j not in dict1:
			dict1[j] = s.count(j)
	for j in dict1:
		if dict1[j] == 1:
			odd += 1
		elif dict1[j] % 2 == 0:
			even += dict1[j] // 2
		else:
			even += dict1[j] // 2
			odd += 1
	if odd > even:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	arr = [w for w in input()]
	from collections import Counter
	d = Counter(arr)
	(ava, req) = (0, 0)
	for (k, v) in d.items():
		req = req + v % 2
		ava = ava + v // 2
	if req <= ava:
		print('YES')
	else:
		print('NO')


t = int(input())
while t != 0:
	s = input()
	d = {}
	for j in s:
		if j not in d:
			d[j] = 1
		else:
			d[j] += 1
	l = list(d.values())
	if 1 not in l:
		print('YES')
	else:
		e = 0
		o = 0
		for j in l:
			if j % 2 == 0:
				e += j // 2
			else:
				e += j // 2
				o += 1
		if o <= e:
			print('YES')
		else:
			print('NO')
	t = t - 1


for t in range(int(input())):
	s = input()
	a = [0] * 26
	for i in s:
		a[ord(i) - 97] += 1
	for i in range(26):
		a[i] %= 2
	if (len(s) - sum(a)) / 2 < sum(a):
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	s = input()
	freq = {}
	for j in s:
		if j not in freq:
			freq[j] = 1
		else:
			freq[j] += 1
	l = list(freq.values())
	if 1 not in l:
		print('YES')
	else:
		evencount = 0
		oddcount = 0
		for j in l:
			if j % 2 == 0:
				evencount += j // 2
			else:
				evencount += j // 2
				oddcount += 1
		if oddcount <= evencount:
			print('YES')
		else:
			print('NO')


t = int(input())
for i in range(t):
	d = [0] * 26
	s = input()
	for i in range(len(s)):
		d[ord(s[i]) - ord('a')] += 1
	even = 0
	odd = 0
	for i in d:
		if i % 2 != 0:
			odd += 1
		elif i != 0:
			even += 1
	total = len(s) - odd
	total = total // 2
	if total >= odd:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	dct = {}
	for i in range(len(s)):
		if dct.get(s[i]) == None:
			dct[s[i]] = 1
		else:
			dct[s[i]] += 1
	odd = 0
	for i in dct.keys():
		if dct[i] % 2 != 0:
			odd += 1
	len_ = len(s) - odd
	len_ = len_ // 2
	if len_ < odd:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = list(input())
	s.sort()
	flag = True
	for i in set(s):
		if s.count(i) < 2:
			flag = False
			break
	if flag == True:
		print('YES')
	else:
		p = 0
		up = 0
		for i in set(s):
			p += s.count(i) // 2
			up += s.count(i) % 2
		if up <= p:
			print('YES')
		else:
			print('NO')


def prog_name():
	s = input()
	final = []
	paired = 0
	unpaired = 0
	for x in s:
		if x not in final:
			paired += s.count(x) // 2
			unpaired += s.count(x) % 2
			final.append(x)
	if paired >= unpaired:
		print('YES')
	else:
		print('NO')
t = int(input())
for unique in range(t):
	prog_name()


def palpal(s):
	mydict = {}
	odd = 0
	even = 0
	for char in s:
		if char in mydict:
			mydict[char] += 1
		else:
			mydict[char] = 1
	for key in mydict:
		if mydict[key] % 2 == 0:
			even += int(mydict[key] / 2)
		else:
			even += mydict[key] // 2
			odd += 1
	if even >= odd:
		return 'YES'
	else:
		return 'NO'
T = int(input())
for i in range(T):
	s = str(input())
	print(palpal(s))


from collections import Counter
for _ in range(int(input())):
	s = input()
	d = Counter(s)
	x2 = 0
	x1 = 0
	for i in d.keys():
		if d[i] > 1 and d[i] % 2 == 0:
			x2 += d[i] // 2
		elif d[i] > 1 and d[i] % 2 != 0:
			x2 += d[i] // 2
			x1 += 1
		elif d[i] <= 1:
			x1 += 1
	if x2 >= x1:
		print('YES')
	else:
		print('NO')


from collections import Counter
t = int(input())
while t:
	s = input()
	d = Counter(s)
	one = 0
	pair = 0
	for i in d.keys():
		if d[i] % 2 == 0:
			pair += d[i] // 2
		elif d[i] == 1:
			one += 1
		else:
			y = d[i] - 3
			pair += y // 2
	if pair >= one:
		print('YES')
	else:
		print('NO')
	t -= 1


for _ in range(int(input())):
	s = input()
	l = [0] * 26
	single = 0
	pair = 0
	for i in range(len(s)):
		l[ord(s[i]) - 97] += 1
	for i in range(26):
		if l[i] == 1:
			single += 1
		else:
			pair += l[i] // 2 - l[i] % 2
	if pair >= single:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	count = {}
	for i in s:
		if i not in count:
			count[i] = 1
		else:
			count[i] += 1
	c1 = c2 = 0
	for i in count:
		c1 += count[i] // 2
		c2 += count[i] % 2
	if c1 < c2:
		print('NO')
	else:
		print('YES')


import sys
import math

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

def I():
	return input()

def II():
	return int(input())

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

def LI():
	return list(map(int, input().split()))
from collections import Counter
for _ in range(II()):
	s = I()
	n = len(s)
	c = Counter(s)
	(x, y) = (0, 0)
	for i in c.values():
		if i == 1:
			x += 1
		if i % 2 == 0:
			y += i // 2
		if i > 3 and i & 1:
			y += (i - 3) // 2
	if y >= x:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	s = input()
	arr = {}
	for i in s:
		if i in arr:
			arr[i] += 1
		else:
			arr[i] = 1
	no_even = 0
	no_odd = 0
	no = 0
	for i in arr:
		if arr[i] % 2:
			no_odd += 1
			no = no + arr[i] // 2
		else:
			no_even += 1
			no = no + arr[i] // 2
	if no >= no_odd:
		print('YES')
	else:
		print('NO')


def palpal(s):
	d = {}
	(odd, even) = (0, 0)
	for ch in s:
		if ch in d:
			d[ch] += 1
		else:
			d[ch] = 1
	for (x, y) in d.items():
		if y % 2 == 0:
			even += y / 2
		else:
			even += y // 2
			odd += 1
	if odd > even:
		return False
	return True
t = int(input())
for i in range(t):
	s = input()
	if palpal(s) == True:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	s = input()
	d = [0 for x in range(26)]
	for x in s:
		d[ord(x) - 97] += 1
	ef = 0
	of = 0
	oof = 0
	for j in range(26):
		if d[j] != 0:
			if d[j] % 2 == 0:
				ef += d[j] // 2
			elif d[j] == 1:
				of += 1
			else:
				ef += (d[j] - 3) // 2
	if ef >= of:
		print('YES')
	else:
		print('NO')


from collections import Counter
for _ in range(int(input())):
	s = input()
	d = Counter(s)
	c = 0
	f = 0
	for item in d.values():
		c = c + item // 2
	for item in d.values():
		if item % 2 != 0:
			f = f + 1
	if f <= c:
		ans = 'YES'
	else:
		ans = 'NO'
	print(ans)


import sys
intinp = lambda : int(input())

def listinp(func=int):
	return list(map(func, input().split()))

def nsepline(n, func=str):
	return [func(input()) for _ in range(n)]

def printlist(li, glue=' '):
	return glue.join(list(map(str, li)))

def fop(s, end='\n'):
	sys.stdout.write(str(s) + end)

def fip():
	return sys.stdin.readline().strip()
fintinp = lambda : int(fip())

def flistinp(func=int):
	return list(map(func, fip().split()))

def fnsepline(n, func=str):
	return [func(fip()) for _ in range(n)]
from collections import defaultdict as df
test_cases = fintinp()
for _ in range(test_cases):
	s = list(input())
	cc = df(int)
	for i in s:
		cc[i] += 1
	pc = oc = 0
	for i in cc.values():
		pc += i // 2
		oc += i % 2
	if pc >= oc:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	temp = {}
	s = input()
	for i in s:
		temp[i] = temp.setdefault(i, 0) + 1
	count1 = 0
	countEven = 0
	for i in temp:
		if temp[i] == 1:
			count1 += 1
		if temp[i] % 2 == 0:
			countEven += temp[i] // 2
		if temp[i] > 1 and temp[i] % 2 == 1:
			countEven += temp[i] // 2
			count1 += 1
	if countEven >= count1:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	a = input()
	b = {}
	for j in a:
		if j not in b:
			b[j] = 0
		b[j] += 1
	single = 0
	even = 0
	for j in b:
		single += b[j] % 2
		even += b[j] // 2
	if single <= even:
		print('YES')
	else:
		print('NO')


from collections import Counter
for _ in range(int(input())):
	s = input().strip()
	c = Counter(s)
	c1 = 0
	cn1 = 0
	for i in c:
		cn1 += c[i] // 2
		c1 += c[i] % 2
	if c1 <= cn1:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	s = input()
	d1 = {}
	for i in s:
		try:
			d1[i] += 1
		except:
			d1[i] = 1
	count = 0
	count1 = 0
	for i in d1:
		count += d1[i] // 2
		d1[i] = d1[i] % 2
	for i in d1:
		count1 += d1[i]
	if count1 <= count:
		print('YES')
	else:
		print('NO')
	t -= 1


for _ in range(0, int(input())):
	strr = input()
	pal = {}
	pair = single = 0
	for i in strr:
		if i in pal:
			pal[i] += 1
		else:
			pal[i] = 1
	for i in pal.values():
		if i % 2 == 0:
			pair += i // 2
		if i == 1:
			single += 1
		if i % 2 != 0 and i > 3:
			pair += (i - 3) // 2
	if pair >= single:
		print('YES')
	else:
		print('NO')


def listed(s):
	d = {}
	for i in s:
		if i not in d:
			d.setdefault(i, 1)
		elif i in d:
			d[i] = d.get(i) + 1
	return d

def rearrange(z):
	count = 0
	even = 0
	for (i, j) in z.items():
		if j == 1:
			count += 1
		else:
			even += j // 2
			count += j % 2
	if even - count >= 0:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	s = input()
	s1 = list(s.lower())
	z = listed(s1)
	rearrange(z)


for _ in range(int(input())):
	hp = {}
	ss = input()
	for i in ss:
		if i in hp:
			hp[i] += 1
		else:
			hp[i] = 1
	e = 0
	o = 0
	for i in hp:
		if hp[i] % 2:
			e += hp[i] // 2
			o += 1
		else:
			e += hp[i] // 2
	if e >= o:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	dic = {}
	for i in s:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	even = 0
	one = 0
	odd = 0
	for i in dic.keys():
		if dic[i] == 1:
			one += 1
		elif dic[i] % 2 == 0:
			even += dic[i] // 2
		elif dic[i] % 2 == 1:
			odd += (dic[i] - 3) // 2
	if one > even + odd:
		print('NO')
	else:
		print('YES')