/** Mock Lab Test for 18th September 2008***/

/*Special prime
Write a program which for an integer n computes and prints the smallest
integer m > n
satisfying all the following conditions simultaneously.
� m is prime.
� m is of the form 3t + 1 for some positive integer t.
� m is also of the form a^2 + b^2 - a*b for some positive integers a, b.
For example,
For input n = 5, the number m is 7 since 7 is prime, 7 = 3 × 2 + 1 and 7 =
32 + 12 -
3 × 1.
For input n = 17, the number m is 19 since 19 is prime, 19 = 3×6+1 and 19
= 52+32-5×3.
Note: The input n must be taken from command line.*/

/* key idea: from the the input n keep on incrementing by 1 and check for
three
conditions one by one.
 *even if one of them fails go to next number
 *Methods isprime(num) : checks whether a number is prime or not
 *                  haveab(num) :  checks for the existence of numbers a
and b such that  a^2 +
b^2 - a*b = num */

class SpecialPrime
{
        static int m,n,t,a,b,sqroot;

        public static boolean isprime(int num)
        {
                int i = 1;

                sqroot = (int)Math.sqrt(num);

                if(num == 2)
		{
                        return true;
		}
		else if( num % 2 == 0)
		{
                        return false;
		}
                else
                {
                        for( i = 3 ; i <= sqroot ; i += 2 )
                        {
                                if (num % i == 0)
				{
					return false;
				}
                        }
                        return true;
                }


        }

        public static boolean haveab(int num)
        {
                int i =1;
                int j =1;

                for( i = 1 ; i <= num; i++ )
                {
                        for( j = 1 ; j  <= num; j++)
                        {
                                if( (i*i+j*j-i*j) == num)
                                {
                                        a=i;
                                        b=j;
					return true;
                                }
                        }
                }
                return false;
        }

        public static void main(String args[])
        {
                n = Integer.parseInt(args[0]);
                t=0;a=0;b=0;sqroot=0;

		if(n%3 == 1)  /*start with a m such that m%3=1 and increase by 3 every time*/
		{
			m = n;
		}
		else if( n % 3 == 2)
		{
			m = n+2;
		}
		else
		{
			m = n+1;
		}

                while(true)
                {
                        if(isprime(m))
                        {
                        	if(haveab(m))
                                {
                                 	System.out.print("For Input = " + n + ", ");
                                        System.out.print("The number m is " + m + "since " + m + " isPrime,");
                                        System.out.print(m + " = "+ "3x" + (m/3) + " +1 " +" and ");
                                        System.out.print(m + " = "+ a + "^2 + " + b + "^2 -" + a + "x" + b+ ".");
                                        System.out.println();
                                        break;
                                 }
                        }
			m=m+3;
                }

        }
}