DINONUM - Dinostratus Numbers

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

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/

hide comments
2010-07-08 17:24:41 Shaka Shadows
Can the problemsetter explain why even some ACed solution have been resubmitted and have got WA???
2010-07-03 13:49:37 sudipto das
@Vimal poonia:can't find out special cases....plz luk at my forum post...
link:https://www.spoj.pl/forum/viewtopic.php?f=3&t=7750&p=18612&hilit=dinonum#p18612
2010-07-01 08:33:06 Vimal poonia
for all Wa's
please look for special cases
Hope this will help!!!
2010-06-26 07:44:34 sudipto das
ans for 48 yes or no?


answer is no

Last edit: 2010-06-29 01:30:23
2010-06-23 09:39:59 Ninjaflyte
"the element mi,j is a multiple of its neighbors mi-1,j, mi-1,j-1 and mi,j-1 (if they exist)"
Even if one of them exists, the condition needs to be satisfied right?
(i.e like (3,1) has to be a multiple of (2,1) in every Dinostratus matrix)

Last edit: 2010-06-23 09:40:25
2010-06-17 23:22:10 Paulo Roberto Santos de Sousa
You can consider just positives integers.
Test thoroughly your code Ninjaflyte and/or rewrite it.
Yes!

Last edit: 2010-06-23 13:51:27
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.