DINONUM - Dinostratus Numbers

no tags 

Recent archaeological discoveries of researchers from the University of Alberta in Canada showed that a strange sequence of numbers were found on the walls of the pyramids of Egypt, the ruins of Macchu Picchu and the stones of Stonehenge. Intrigued by the apparent coincidence researchers triggered the Department of Mathematics to decipher what were special about that sequence or numbers.

The discovery was startling. All numbers were generated by matrices of Dinostratus. Dinostratus was a famous Greek mathematician who lived from 390 to 320 BC and worked in major geometry problems like squaring the circle. Dinostratus studied matrices M of size 3×3 formed by nine distinct integers with the property that for every position (i, j), i = 1...3, j = 1...3 of matrix, the element mi, j is a multiple of its neighbors mi-1, j, mi-1, j-1 and mi, j-1 (if they exist). In his honor, we say that n is a Dinostratus number if exist a matrix M with the property above such that m3, 3 = n.

See an example with n = 36.

1  2  4
3  6 12
9 18 36

The relationship between the Dinostratus numbers, the pyramids of Egypt, Stonehenge and the stones of the ruins of Machu Picchu still remains a great mystery. But researchers in Alberta are willing to study these magic numbers. Your task is to make a program that receives an integer n and checks whether this is a Dinostratus number.

Input

The input consists of several instances. Each instance is given by a line containing an integer n (1 ≤ n ≤ 1048576). The input ends with end of file.

Output

For each instance, you must print an identifier Instance k, where k is the number of the current instance. On the next line print yes if n is a Dinostratus number otherwise print no.

Example

Input:
36
37
38

Output:
Instance 1
yes
Instance 2
no
Instance 3
no

hide comments
nadstratosfer: 2019-07-07 09:54:47

What Mahmud said, also input and TL. Fun to break down and solve though, enjoyed.

mahmud2690: 2017-02-19 16:36:22

bullshit output

(Tjandra Satria Gunawan)(曾毅昆): 2012-08-08 11:54:21

Because of printing (Yes/No) give me 19 WA!
Finally AC after using (yes/no)! Really silly mistake...

sudipto das: 2010-07-22 08:51:34

got ac atlast,thnx to da author,he really corrected his output set......
to evryone else, luk at my forum post, it really works, it will cause no more WA... :)

.::Manish Kumar::.: 2010-07-22 02:07:05

is m(3,3) always a multiple of 36?

刘启鹏: 2010-07-14 15:39:18

Has the testdata been modified?

RE(myself): (7.21)the testdata has been corrected.

Last edit: 2010-07-21 01:57:05
Shaka Shadows: 2010-07-09 21:36:49

@Paulo Roberto Santos de Sousa
Sorry for being so insistent, but why ACed solutions get WA?? Please mail me for more details, I must respect the rules of comments.

Paulo Roberto Santos de Sousa: 2010-07-09 18:58:28

Sorry by not warning.
I modified test cases, adding more criticals cases.
Sorry by inconvenience.
There was an error in my output. I'd changed "no" to "nao" and "yes" by "sim". Plz, resubmit yours solutions because
i could not rejudge.

Last edit: 2010-07-20 14:10:11
Shaka Shadows: 2010-07-08 20:25:59

Still getting WA even with ACed solutions and also printing. Can somebody tell what's happenning???

­Surendra: 2010-07-08 18:49:05

Remember one thing ,
put a blank line after each test case.


Added by:Paulo Roberto Santos de Sousa
Date:2010-06-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 ERL JS-RHINO NODEJS OBJC PERL6 SCALA SQLITE TCL VB.NET
Resource:http://br.spoj.pl/problems/DINOSTRA/