Project Euler #98: Anagramic squares

_{This problem is a programming version of Problem 98 from projecteuler.net}

Some square numbers are numerical anagrams of other square numbers. For instance, and . The set of square anagrams of is .

For each value of , we wish to know the largest set of square anagrams for a number with digits. Print out the largest number of this set. If the largest set is not unique, pick whichever one has the largest maximum element.

Input Format

The only number - the length of the needed anagram.

Output Format

The -digit number which is the largest square with the most anagramic squares of length .

Sample Input

Sample Output