For a string $S$ let the unique set of characters that occur in it one or more times be $C$. Consider a permutation of the elements of $C$ as $(c_1, c_2, c_3 ... )$. Let $f(c)$ be the number of times $c$ occurs in $S$.
If any such permutation of the elements of $C$ satisfies $f(c_i) = f(c_{i-1}) + f(c_{i-2})$ for all $i \ge 3$, the string is said to be a dynamic string.
Mr Bancroft is given the task to check if the string is dynamic, but he is busy playing with sandpaper. Would you help him in such a state?
Note that if the number of distinct characters in the string is less than 3, i.e. if $|C| < 3$, then the string is always dynamic.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, a string $S$.

-----Output:-----
For each testcase, output in a single line "Dynamic" if the given string is dynamic, otherwise print "Not". (Note that the judge is case sensitive)

-----Constraints-----
- $1 \leq T \leq 10$
- $1 \leq |S| \leq 10^5$
- $S$ contains only lower case alphabets: $a$, $b$, …, $z$

-----Sample Input:-----
3
aaaabccc
aabbcc
ppppmmnnoooopp

-----Sample Output:-----
Dynamic
Not
Dynamic

-----Explanation:-----
- Testase 1: For the given string, $C = \{a, b, c\}$ and $f(a)=4, f(b)=1, f(c)=3$. $f(a) = f(c) + f(b)$ so the permutation $(b, c, a)$ satisfies the requirement.
- Testcase 2: Here too $C = \{a, b, c\}$ but no permutation satisfies the requirement of a dynamic string.
- Testcase 3: Here $C = \{m, n, o, p\}$ and $(m, n, o, p)$ is a permutation that makes it a dynamic string.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Sorting

Data structures


Solutions:
from collections import Counter

def fib_str(s):
	counts = Counter(s)
	if len(counts) < 3:
		return True
	[x, y, z] = counts.most_common(3)
	if x[1] == y[1] + z[1]:
		return True
	return False
test = int(input())
for _ in range(test):
	s = input()
	if fib_str(s):
		print('Dynamic')
	else:
		print('Not')


for i in range(int(input())):
	inp = input()
	inpSet = set(inp)
	if len(inpSet) < 3:
		print('Dynamic')
		continue
	charList = []
	for i in inpSet:
		charList.append((i, inp.count(i)))
	charList = sorted(charList, key=lambda x: x[1], reverse=True)
	flag = False
	if charList[0][1] == charList[1][1] + charList[2][1]:
		flag = True
	if flag:
		print('Dynamic')
	else:
		print('Not')


from itertools import permutations
for _ in range(int(input())):
	st = input()
	s = set(st)
	l = []
	for i in set(s):
		l.append(st.count(i))
	l.sort()
	if len(l) < 3 or l[-1] == l[-2] + l[-3]:
		print('Dynamic')
	else:
		print('Not')


from collections import Counter

def fib_str(s):
	count = Counter(s)
	if len(count) < 3:
		return True
	[a, b, c] = count.most_common(3)
	if a[1] == b[1] + c[1]:
		return True
	return False

def __starting_point():
	test = int(input())
	for _ in range(test):
		s = input()
		if fib_str(s):
			print('Dynamic')
		else:
			print('Not')
__starting_point()


from collections import Counter
for _ in range(int(input())):
	o = input()
	c = []
	d = dict(Counter(o))
	for e in d.values():
		c.append(e)
	c.sort()
	if len(c) < 3:
		print('Dynamic')
	elif c[-1] != c[-2] + c[-3]:
		print('Not')
	else:
		print('Dynamic')


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 = RW()
	freq = sorted(Counter(inps).values())
	if len(freq) < 3:
		print('Dynamic')
	else:
		lens = len(freq)
		if lens >= 4 and freq[3] != freq[1] + freq[2]:
			(freq[0], freq[1]) = (freq[1], freq[0])
		answer = 'Dynamic'
		for i in range(2, len(freq)):
			if freq[i] != freq[i - 1] + freq[i - 2]:
				answer = 'Not'
				break
		print(answer)


for tc in range(int(input())):
	s = input()
	c = set(s)
	l = []
	for i in c:
		l.append(s.count(i))
	if len(l) < 3:
		print('Dynamic')
	else:
		l.sort()
		if l[-1] == l[-2] + l[-3]:
			print('Dynamic')
		else:
			print('Not')


for _ in range(int(input())):
	d = {}
	s = input().strip()
	for i in s:
		try:
			d[i] += 1
		except:
			d[i] = 1
	d = list(d.values())
	d.sort()
	if len(d) < 3:
		print('Dynamic')
	else:
		for i in range(2, len(d)):
			flag = 0
			if d[i - 1] + d[i - 2] == d[i]:
				continue
			else:
				(d[0], d[1]) = (d[1], d[0])
				for i in range(2, len(d)):
					if d[i - 1] + d[i - 2] == d[i]:
						continue
					else:
						print('Not')
						flag = 1
						break
				if flag == 1:
					break
		else:
			print('Dynamic')


T = int(input())
for i in range(T):
	S = input()
	l1 = []
	for i in set(S):
		l1 = l1 + [S.count(i)]
	l1.sort()
	if len(l1) < 3:
		print('Dynamic')
		continue
	if l1[-3] + l1[-2] != l1[-1]:
		print('Not')
		continue
	else:
		print('Dynamic')


t = int(input())
for i in range(t):
	s = input()
	lst = []
	for i in set(s):
		lst.append(s.count(i))
	lst.sort()
	if len(lst) < 3 or lst[-1] == lst[-2] + lst[-3]:
		print('Dynamic')
	else:
		print('Not')


for _ in range(int(input())):
	a = input()
	d = {}
	for i in a:
		if i in d:
			d.update({i: d.get(i) + 1})
		else:
			d.update({i: 1})
	l = []
	for i in d.values():
		l.append(i)
	l.sort()
	if len(l) < 3:
		print('Dynamic')
	elif l[-1] == l[-2] + l[-3]:
		print('Dynamic')
	else:
		print('Not')


for _ in range(int(input())):
	s = input()
	s2 = list(s)
	s1 = list(set(s))
	a = []
	for i in s1:
		a.append(s2.count(i))
	a = sorted(a)
	if len(a) < 3:
		print('Dynamic')
	else:
		for i in range(len(a) - 1, 1, -1):
			if a[i] == a[i - 1] + a[i - 2]:
				print('Dynamic')
				break
			else:
				print('Not')
				break


for _ in range(int(input())):
	x = input()
	y = [x.count(z) for z in set(x)]
	y.sort()
	if len(y) < 3:
		print('Dynamic')
		continue
	print('Not') if y[-3] + y[-2] != y[-1] else print('Dynamic')


def dynamic_check(t_case):
	func_tcase = []
	t_case = t_case.replace(' ', '')
	list_set = list(set(t_case))
	for item in list_set:
		func_tcase.append(t_case.count(item))
	print(func(func_tcase))

def func(func_tcase):
	if len(func_tcase) < 3:
		return 'Dynamic'
	else:
		func_tcase.sort()
		if func_tcase[-1] == func_tcase[-2] + func_tcase[-3]:
			return 'Dynamic'
		return 'Not'
n_cases = int(input())
for _ in range(n_cases):
	t_case = input()
	dynamic_check(t_case)


for _ in range(int(input())):
	s = input()
	l = []
	for i in set(s):
		l.append(s.count(i))
	l = sorted(l)
	if len(l) < 3 or l[-1] == l[-2] + l[-3]:
		print('Dynamic')
	else:
		print('Not')


import sys
import math

def isDynamic(arr):
	for i in range(2, len(arr)):
		if arr[i] != arr[i - 1] + arr[i - 2]:
			return False
	return True

def main(arr):
	freq = {}
	for e in arr:
		if e not in freq:
			freq[e] = 0
		freq[e] += 1
	new_arr = []
	for e in freq:
		new_arr.append(freq[e])
	new_arr.sort()
	if len(arr) <= 2:
		return 'Dynamic'
	a = isDynamic(new_arr)
	(new_arr[0], new_arr[1]) = (new_arr[1], new_arr[0])
	b = isDynamic(new_arr)
	if a or b:
		return 'Dynamic'
	return 'Not'
for _ in range(int(input())):
	print(main(input()))


from collections import Counter
for _ in range(int(input())):
	s = input()
	dict1 = dict(Counter(s))
	l1 = []
	for i in dict1.values():
		l1.append(i)
	l1.sort()
	check = True
	if len(set(s)) < 3:
		print('Dynamic')
	else:
		if l1[-1] == l1[-2] + l1[-3]:
			print('Dynamic')
			check = False
		if check:
			print('Not')


n = int(input())
for i in range(n):
	s = input()
	res = []
	for i in set(s):
		res.append(s.count(i))
	res.sort()
	if len(res) < 3 or res[-1] == res[-2] + res[-3]:
		print('Dynamic')
	else:
		print('Not')


for _ in range(int(input())):
	s = input()
	c = list(set(s))
	l = []
	for i in c:
		l.append(s.count(i))
	noty = 0
	l.sort()
	if len(l) < 3:
		print('Dynamic')
	else:
		for i in range(2, len(l)):
			if i == 3:
				if not l[3] == l[2] + l[1] and (not l[3] == l[2] + l[0]):
					noty = 1
					break
			elif l[i - 1] + l[i - 2] != l[i]:
				noty = 1
				break
		if noty:
			print('Not')
		else:
			print('Dynamic')


for y in range(int(input())):
	a = input()
	k = [a.count(i) for i in set(a)]
	k.sort()
	if len(k) < 3:
		print('Dynamic')
		continue
	if k[-3] + k[-2] != k[-1]:
		print('Not')
		continue
	else:
		print('Dynamic')


for i in range(int(input())):
	s = input()
	ss = set(s)
	if len(ss) < 3:
		print('Dynamic')
		continue
	l = []
	for i in ss:
		l.append((i, s.count(i)))
	l = sorted(l, key=lambda x: x[1], reverse=True)
	f = False
	if l[0][1] == l[1][1] + l[2][1]:
		f = True
	if f:
		print('Dynamic')
	else:
		print('Not')


try:
	for _ in range(int(input())):
		s = input()
		c = list(set(s))
		l = []
		for i in c:
			l.append(s.count(i))
		noty = 0
		l.sort()
		if len(l) < 3:
			print('Dynamic')
		else:
			for i in range(2, len(l)):
				if i == 3:
					if not l[3] == l[2] + l[1] and (not l[3] == l[2] + l[0]):
						noty = 1
						break
				elif l[i - 1] + l[i - 2] != l[i]:
					noty = 1
					break
			if noty:
				print('Not')
			else:
				print('Dynamic')
except EOFError as e:
	pass


from collections import Counter
n = int(input())
for i in range(n):
	str = input()
	a = Counter(str)
	l = list(a.values())
	l.sort()
	if len(l) < 3:
		print('Dynamic')
	elif l[-1] == l[-2] + l[-3]:
		print('Dynamic')
	else:
		print('Not')


t = int(input())
while t:
	t -= 1
	s = input()
	l = []
	l1 = []
	lik = 2
	for i in s:
		if i not in l:
			l.append(i)
	for i in l:
		l1.append(s.count(i))
	if len(l) < 3:
		lik = 0
	if lik == 2:
		l1.sort()
		if l1[-2] + l1[-3] != l1[-1]:
			lik = 1
	if lik == 0 or lik == 2:
		print('Dynamic')
	if lik == 1:
		print('Not')


def fibFound(x):
	found = True
	if x[-1] != x[-2] + x[-3]:
		found = False
	return found

def dyn(s):
	res = False
	u = [s.count(x) for x in set(s)]
	if len(u) < 3 or fibFound(sorted(u)):
		return True
	else:
		return False
try:
	t = int(input())
	for i in range(0, t):
		s = input()
		if dyn(s):
			print('Dynamic')
		else:
			print('Not')
except EOFError as e:
	pass


t = int(input())
for i in range(t):
	s = input()
	p = set(s)
	l = []
	for i in p:
		l.append(s.count(i))
	l.sort()
	if len(l) >= 4 and l[3] != l[1] + l[2]:
		(l[0], l[1]) = (l[1], l[0])
	ok = True
	if len(l) >= 3:
		for i in range(2, len(l)):
			if l[i] != l[i - 1] + l[i - 2]:
				ok = False
	if ok:
		print('Dynamic')
	else:
		print('Not')


T = int(input())
for tj in range(T):
	s = input()
	N = len(s)
	count = [0] * 26
	for i in range(N):
		count[ord(s[i]) - ord('a')] += 1
	convert_table = []
	for i in range(26):
		if count[i] != 0:
			convert_table.append(count[i])
	if len(convert_table) < 3:
		print('Dynamic')
	else:
		convert_table.sort()
		flag = True
		for i in range(2, len(convert_table)):
			if i == 3:
				if convert_table[i] != convert_table[i - 1] + convert_table[i - 2] and convert_table[i] != convert_table[i - 1] + convert_table[i - 3]:
					flag = False
					break
			elif convert_table[i] != convert_table[i - 1] + convert_table[i - 2]:
				flag = False
				break
		if flag:
			print('Dynamic')
		else:
			print('Not')


n = int(input())
for i in range(n):
	s = input()
	l = list(s)
	t = set(l)
	d = {}
	l1 = []
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for i in d.values():
		l1.append(i)
	l1.sort()
	N = len(l1)
	if N >= 4 and l1[3] != l1[1] + l1[2]:
		(l1[0], l1[1]) = (l1[1], l1[0])
	ok = True
	if N >= 3:
		for i in range(2, N):
			if l1[i] != l1[i - 1] + l1[i - 2]:
				ok = False
	if ok:
		print('Dynamic')
	else:
		print('Not')


t = int(input().strip())
for k in range(t):
	s = input().strip()
	d = {}
	maxx = -10000
	cu = c = 0
	for i in s:
		if i not in d:
			cu += 1
			d[i] = 1
		else:
			d[i] += 1
	if cu < 3:
		print('Dynamic')
	else:
		lii = list(d.values())
		lii.sort()
		for i in range(2, len(lii)):
			if lii[i] == lii[i - 1] + lii[i - 2]:
				c = 1
			else:
				c = 0
		(lii[0], lii[1]) = (lii[1], lii[0])
		for i in range(2, len(lii)):
			if lii[i] == lii[i - 1] + lii[i - 2]:
				c = 1
			else:
				c = 0
		if c == 0:
			print('Not')
		else:
			print('Dynamic')


from collections import Counter
t = int(input())
for i in range(t):
	s = input()
	d = Counter(s)
	d = d.values()
	d = list(d)
	flag = 1
	d.sort()
	for i in range(2, len(d)):
		if i == 3:
			if d[i] != d[i - 1] + d[i - 2] and d[i] != d[i - 1] + d[i - 3]:
				flag = 0
				break
		elif d[i] != d[i - 1] + d[i - 2]:
			flag = 0
			break
	if len(d) < 3:
		print('Dynamic')
	elif flag:
		print('Dynamic')
	else:
		print('Not')


from collections import Counter
T = int(input())
for _ in range(T):
	n = input()
	c = 0
	r = Counter(n)
	L = []
	for j in r.keys():
		L.append(r[j])
	L.sort()
	if len(L) >= 4 and L[1] + L[2] != L[3]:
		temp = L[0]
		L[0] = L[1]
		L[1] = temp
	fl = True
	if len(L) >= 3:
		for i in range(len(L) - 2):
			if L[i + 2] != L[i] + L[i + 1]:
				fl = False
	if fl:
		print('Dynamic')
	else:
		print('Not')


for _ in range(int(input())):
	s = input()
	d = {}
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	l = []
	for i in d.values():
		l.append(i)
	l.sort()
	if len(l) < 3:
		print('Dynamic')
	elif l[-1] == l[-2] + l[-3]:
		print('Dynamic')
	else:
		print('Not')


from collections import Counter
for _ in range(int(input())):
	s = str(input())
	s1 = Counter(s)
	a = list(s1.values())
	a.sort(reverse=True)
	if len(a) < 3:
		print('Dynamic')
	elif a[0] != a[1] + a[2]:
		print('Not')
	else:
		print('Dynamic')


t = int(input())
for _ in range(t):
	s = input()
	arr_dic = {}
	for i in range(len(s)):
		if s[i] not in arr_dic:
			arr_dic[s[i]] = 1
		else:
			arr_dic[s[i]] += 1
	counter = 0
	arr = sorted(list(arr_dic.values()), reverse=True)
	if len(arr) < 3:
		print('Dynamic')
	else:
		for i in range(0, len(arr) - 2):
			if i != len(arr) - 4:
				if arr[i] != arr[i + 1] + arr[i + 2]:
					counter = 1
			elif arr[i] != arr[i + 1] + arr[i + 2]:
				c = arr[i + 3]
				arr[i + 3] = arr[i + 2]
				arr[i + 2] = c
				if arr[i] != arr[i + 1] + arr[i + 2]:
					counter = 1
		if counter == 0:
			print('Dynamic')
		else:
			print('Not')


t = int(input())
for _ in range(t):
	s = input()
	s_dict = dict()
	for i in range(len(s)):
		s_dict[s[i]] = s_dict.get(s[i], 0) + 1
	values = list(s_dict.values())
	values.sort()
	if len(values) >= 3:
		ans = 'Dynamic'
		for i in range(2, len(values)):
			if i == 3 and (values[0] + values[2] == values[3] or values[1] + values[2] == values[3]):
				continue
			if values[i] != values[i - 1] + values[i - 2]:
				ans = 'Not'
				break
		print(ans)
	else:
		print('Dynamic')


def check_fib(lis):
	is_fib = True
	for i in range(2, len(lis)):
		if lis[i] != lis[i - 1] + lis[i - 2]:
			is_fib = False
			break
	if is_fib:
		return True
	(lis[0], lis[1]) = (lis[1], lis[0])
	for i in range(2, len(lis)):
		if lis[i] != lis[i - 1] + lis[i - 2]:
			return False
	return True
t = int(input())
for _ in range(t):
	s = input()
	freq_list = [s.count(x) for x in set(s)]
	if len(freq_list) < 3:
		print('Dynamic')
		continue
	freq_list.sort()
	if check_fib(freq_list):
		print('Dynamic')
	else:
		print('Not')


t = int(input())
for _ in range(t):
	s = [x for x in input()]
	c = list(set(s))
	a = []
	for i in c:
		a.append(s.count(i))
	a.sort()
	if len(a) < 3:
		print('Dynamic')
	else:
		for i in range(len(a) - 1, 1, -1):
			if a[i] == a[i - 1] + a[i - 2]:
				print('Dynamic')
				break
			else:
				print('Not')
				break


t = int(input())
for _ in range(t):
	st = input()
	s = set(st)
	a = []
	f1 = f2 = 0
	for i in s:
		a.append(st.count(i))
	a.sort()
	if len(a) >= 3:
		for i in range(2, len(a)):
			if a[i] != a[i - 1] + a[i - 2]:
				f1 = 1
				break
		x = a[0]
		a[0] = a[1]
		a[1] = x
		for i in range(2, len(a)):
			if a[i] != a[i - 1] + a[i - 2]:
				f2 = 1
				break
		if f1 == 1 and f2 == 1:
			print('Not')
		else:
			print('Dynamic')
	else:
		print('Dynamic')


t = int(input())
for i in range(t):
	s = input()
	l1 = []
	for i in set(s):
		l1 = l1 + [s.count(i)]
	l1.sort()
	if len(l1) < 3:
		print('Dynamic')
		continue
	if l1[-3] + l1[-2] != l1[-1]:
		print('Not')
		continue
	else:
		print('Dynamic')


from collections import Counter
for i in range(int(input())):
	s = str(input())
	d = Counter(s)
	x = list(d.values())
	x.sort()
	if len(x) < 3:
		print('Dynamic')
	elif x[-1] == x[-3] + x[-2]:
		print('Dynamic')
	else:
		print('Not')


from collections import defaultdict
from sys import stdin, stdout

def fastIO():
	input = stdin.readline
	return input().rstrip('\r\n')

def fastOut(t):
	stdout.write(str(t) + '\n')
for _ in range(int(fastIO())):
	S = fastIO()
	d = defaultdict(lambda : 0)
	for i in range(len(S)):
		d[S[i]] += 1
	d = sorted(list(d.values()))
	if len(d) >= 4:
		if d[1] + d[2] != d[3]:
			(x, y) = (d[0], d[1])
			(d[0], d[1]) = (y, x)
	for i in range(2, len(d)):
		if d[i] != d[i - 1] + d[i - 2]:
			print('Not')
			break
	else:
		print('Dynamic')


for _ in range(int(input())):
	xd = {}
	x = input()
	for i in range(len(x)):
		xd[x[i]] = xd.setdefault(x[i], 0) + 1
	xd = sorted(xd.values())
	if len(xd) <= 2:
		print('Dynamic')
		continue
	ans = 'Dynamic'
	if len(xd) >= 4 and xd[3] != xd[2] + xd[1]:
		(xd[0], xd[1]) = (xd[1], xd[0])
	for j in range(2, len(xd)):
		if xd[j - 2] + xd[j - 1] != xd[j]:
			ans = 'Not'
			break
	print(ans)


from collections import Counter
for t in range(int(input())):
	S = input()
	f = [y for (x, y) in Counter(S).most_common()]
	f = f[::-1]
	if len(f) > 3 and f[3] != f[2] + f[1]:
		(f[0], f[1]) = (f[1], f[0])
	ok = len(f) < 3 or all((f[i] == f[i - 1] + f[i - 2] for i in range(2, len(f))))
	print('Dynamic' if ok else 'Not')


for _ in range(int(input())):
	a = input()
	b = [a.count(i) for i in set(a)]
	b.sort()
	if len(b) < 3:
		print('Dynamic')
		continue
	if b[-3] + b[-2] != b[-1]:
		print('Not')
		continue
	else:
		print('Dynamic')


for _ in range(int(input())):
	x = input()
	y = list(set(x))
	l = []
	for i in y:
		l.append(x.count(i))
	temp = 0
	l.sort()
	if len(l) < 3:
		print('Dynamic')
	else:
		for i in range(2, len(l)):
			if i == 3:
				if not l[3] == l[2] + l[1] and (not l[3] == l[2] + l[0]):
					temp = 1
					break
			elif l[i - 1] + l[i - 2] != l[i]:
				temp = 1
				break
		if temp:
			print('Not')
		else:
			print('Dynamic')


from collections import Counter
for _ in range(int(input())):
	s = input()
	d = Counter(s)
	a = sorted(list(d.values()))
	l = len(a)
	if len(s) < 3:
		print('Dynamic')
	elif a[l - 1] == a[l - 2] + a[l - 3]:
		print('Dynamic')
	else:
		print('Not')


from collections import Counter
for _ in range(int(input())):
	s = input()
	d = Counter(s)
	o = list(d.values())
	o.sort()
	if len(o) < 3:
		print('Dynamic')
	elif o[-1] != o[-3] + o[-2]:
		print('Not')
	else:
		print('Dynamic')


from collections import Counter
t = int(input())
for _ in range(t):
	s = str(input())
	sc = Counter(s)
	v = list(sc.values())
	v.sort()
	if len(v) < 3:
		print('Dynamic')
	else:
		isd = True
		for i in range(2, len(v)):
			if i == 3:
				if v[i - 1] + v[i - 2] != v[i] and v[i - 1] + v[i - 3] != v[i]:
					isd = False
			elif v[i - 1] + v[i - 2] != v[i]:
				isd = False
		if isd == True:
			print('Dynamic')
		else:
			print('Not')


def activate(x):
	y = True
	if x[-1] != x[-2] + x[-3]:
		y = False
	return y

def activation(a):
	z = False
	count = [a.count(d) for d in set(a)]
	if len(count) < 3 or activate(sorted(count)):
		return True
	else:
		return False
t = int(input())
for i in range(t):
	s = input()
	if activation(s):
		print('Dynamic')
	else:
		print('Not')


t = int(input())
for i in range(t):
	set_str = set()
	set_dir = dict()
	str_in = input()
	for j in str_in:
		set_str.add(j)
	set_dir = {k: str_in.count(k) for k in set_str}
	a = sorted(set_dir.values())
	flag = 1
	if len(a) >= 4 and a[3] != a[2] + a[1]:
		(a[1], a[0]) = (a[0], a[1])
	for i in range(2, len(a)):
		if a[i] != a[i - 1] + a[i - 2]:
			flag = 2
			break
	if flag == 1 or len(set_str) < 3:
		print('Dynamic')
	else:
		print('Not')


T = int(input())
for _ in range(T):
	s = list(input())
	d = {}
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	M = []
	for i in d:
		M.append(d[i])
	M.sort()
	if len(M) < 3:
		print('Dynamic')
	else:
		found = True
		for i in range(2, len(M)):
			if M[i] == M[i - 1] + M[i - 2]:
				pass
			elif i == 3:
				if M[i] == M[2] + M[0]:
					pass
				else:
					found = False
					break
			else:
				found = False
				break
		if found:
			print('Dynamic')
		else:
			print('Not')