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 (c1,c2,c3…). Let f(c) be the number of times c occurs in S.

If any such permutation of the elements of C satisfies f(ci)=f(ci−1)+f(ci−2) for all i≥3, the string is said to be a dynamic string.

Mr Hardik 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 contain T, number of testcases. Then the testcases
Each testcase contains of a single line of input, a string S.
**Output:**
For each testcase, output print "Dynamic" if the given string is dynamic, otherwise print "Not". (Note that the judge is case sensitive)

#include <stdio.h> #include <string.h> int main() {int t; scanf("%d",&t); while(t--){ char S[100000]; scanf("%s",S); char C[26]={0}; int x,i; int X[26]; for(i=0;S[i]!='\0';i++){ x=S[i]-'a'; C[x]++; } int count=0,j=0; for(i=0;i<26;i++){ if(C[i]!=0){ X[j]=C[i]; count++; j++; } } if(count<3){ printf("Dynamic\n"); continue; } int round,temp,flag; for(round=1;round<=count-1;round++){ flag=0; for(i=0;i<=count-1-round;i++){ if(X[i]>X[i+1]){ flag=1; temp=X[i]; X[i]=X[i+1]; X[i+1]=temp; } } if(flag==0) break; } int yo=0; for(i=count-1;i<count;i++){ if(X[i]!=X[i-1]+X[i-2]){ yo=1; break; } } if(yo==1){ printf("Not\n"); flag=1; } else printf("Dynamic\n"); } return 0; }

**INPUT_1:**

2

ffffgff

ggttrr

**OUTPUT:**

Dynamic

Not

**INPUT_2:**

5

hthehth

feeeefe

tttyyyt

uuuiuii

ccyycci

**OUTPUT:**

Not

Dynamic

Dynamic

Dynamic

Not

**ILLUSTRATION**