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.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
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")

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")
 
 
 
 


# cook your dish here
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()

# cook your dish here
# cook your dish here
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

def __starting_point():
 test = int(input())

 for _ in range(test):
  s = input()

  if fib_str(s):
   print("Dynamic")
  else:
   print("Not")
__starting_point()

# cook your dish here
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

def __starting_point():
 test = int(input())

 for _ in range(test):
  s = input()

  if fib_str(s):
   print("Dynamic")
  else:
   print("Not")
__starting_point()

# cook your dish here
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

def __starting_point():
 test = int(input())

 for _ in range(test):
  s = input()

  if fib_str(s):
   print("Dynamic")
  else:
   print("Not")
__starting_point()

# cook your dish here
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

def __starting_point():
 test = int(input())

 for _ in range(test):
  s = input()

  if fib_str(s):
   print("Dynamic")
  else:
   print("Not")
__starting_point()

# cook your dish here
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

def __starting_point():
 test_n = int(input())

 for _ in range(test_n):
  s = input()

  if fib_str(s):
   print("Dynamic")
  else:
   print("Not")
__starting_point()

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

def __starting_point():
 test_n = int(input())

 for _ in range(test_n):
  s = input()

  if fib_str(s):
   print("Dynamic")
  else:
   print("Not")

__starting_point()

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")

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")


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")


# cook your dish here
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")


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")


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")

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())):
 s=input()
 t=[]
 for i in set (s):
  t.append(s.count(i))
 t=sorted(t)
 if len(t)<3 or t[-1]==t[-2]+t[-3]:
  print('Dynamic')
 else:
  print('Not')
# cook your dish here


# cook your dish here
# cook your dish here
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')

# cook your dish here
# cook your dish here
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()
 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')


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')

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')