INTNOS - Interesting or Not

no tags 

 

Krishna, the math geek of our class thinks that the number 41312432 is interesting.
This is because of the following property: 
There is exactly 1 digit between the two 1s, there are exactly 2 digits between the two 2s, and so on. 
Formally, Krishna thinks that a number X is interesting if the following property is satisfied: 
For each D between 0 and 9, inclusive, X either does not contain the digit D at all, or it contains exactly 
two digits D, and there are precisely D other digits between them.   
You are given a String X that contains the digits of a positive integer. Print "Interesting" if that integer is interesting, otherwise print "Not interesting" ( Quotes for clarity ).
 Input
First line contains a single integer T, the number of test cases. It is followed by T cases each of which contains one string
 Output
For each test case output a single line containing "Interesting" (without quotes) if it is an interesting integer or "Not interesting" (without quotes) if it is not interesting.
Constraints
1<=T<=50
The length of the string will not exceed 20.
Example
Input:
3
2002
1001
41312432
Output:
Interesting
Not interesting
Interesting
Explanation for test case #1:
There are 0 digits between the two 0s, and 2 digits between the two 2s, so interesting.
 
Explanation for test case #2:
There should be 1 digit between the two 1s, but there are 2 digits between the two 1s, so not interesting.

Krishna, the math geek of our class thinks that the number 41312432 is interesting.

This is because of the following property: 

There is exactly 1 digit between the two 1s, there are exactly 2 digits between the two 2s, and so on. 

Formally, Krishna thinks that a number X is interesting if the following property is satisfied: 

For each D between 0 and 9, inclusive, X either does not contain the digit D at all, or it contains exactly two digits D, and there are precisely D other digits between them.   

You are given a String X that contains the digits of a positive integer. Print "Interesting" if that integer is interesting, otherwise print "Not interesting" ( Quotes for clarity ).


Input

First line contains a single integer T, the number of test cases. It is followed by T cases each of which contains one string.


 Output

For each test case output a single line containing "Interesting" (without quotes) if it is an interesting integer or "Not interesting" (without quotes) if it is not interesting.


Constraints

1<=T<=50

The length of the string will not exceed 20.


Example


Input:

3

2002

1001

41312432


Output:

Interesting

Not interesting

Interesting


Explanation for test case #1:

There are 0 digits between the two 0s, and 2 digits between the two 2s, so interesting.

 

 Explanation for test case #2:

There should be 1 digit between the two 1s, but there are 2 digits between the two 1s, so not interesting.

 


hide comments
Mitch Schwartz: 2014-05-03 19:57:29

Time limit is not reasonable for languages with interpreter startup time, and the task is tutorial-level. Moved.

knb_dtu: 2014-05-03 19:48:15

what will be the output for 587?

venky: 2014-04-26 17:44:32

Accepted at first attempt..Nice problem :)


Added by:785227
Date:2014-03-18
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET