beecrowd | 1801 | [Univ]

Playing with Numbers

By Fidel I. Schaposnik Massolo, Universidad Nacional de La Plata AR Argentina

Timelimit: 3

Prof. Cedrado-Cueta likes to play with numbers, and he is particularly fond of perfect squares. A natural number n is said to be a perfect square if there exists a natural number m such that n = m2. For example, 9 and 36 are perfect squares because 9 = 32 and 36 = 62, whereas 5 and 12 are not perfect squares.

The Prof. recently found a number x, and he would like to create a perfect square using it. In order to do so, he will reorder the digits of x to form some number y, and then calculate n = x + y. In how many ways is it possible for him to obtain a perfect square as the value of n? For example, if x = 29 the Prof. can take y = 92, so that n = 29 + 92 = 121 = 112.

Note that when reordering the digits of x the Prof. should use all its digits and obtain a correct expression for the number y, i.e. there can be no leading 0's in y. Also note that he may choose to keep the digits of x in the same order, effectively getting for y the same value as x.


The input consists of a single line containing one positive integer number x with at most 12 digits.


The output consists of a single line containing one integer number representing the number of ways in which the Prof. can obtain a perfect square as the value of n. Two ways are considered different if they differ in the value of n obtained.

Input Samples Output Samples