Số chính phương là bình phương của một số nguyên. Ví dụ, ~1 = 1^2~, ~4870849 = 2207^2~ và ~31393609 = 5603^2~ là các số chính phương, còn ~2~, ~8~ hay ~10~ thì không. Trong bài toán này, ta chỉ xét các số chính phương là bình phương của một số nguyên dương.

Ta gọi một số là số chính phương không lặp lại khi và chỉ khi số đó là số chính phương và trong biểu diễn của số đó trong hệ thập phân, không có chữ số nào xuất hiện nhiều hơn một lần. Ví dụ, ~25 = 5^2~, ~36 = 6^2~ và ~49 = 7^2~ là các số chính phương không lặp lại, còn ~100 = 10^2~, ~121 = 11^2~ và ~144 = 12^2~ thì không (vì có các chữ số ~0~, ~1~ hay ~4~ xuất hiện nhiều hơn một lần).

Ta viết các số chính phương không lặp lại dương thành một dãy và sắp xếp chúng theo thứ tự tăng dần, ta được dãy ~1, 4, 9, \dots~

Yêu cầu: Cho một số nguyên dương ~k~, hãy tìm số thứ ~k~ trong dãy.

Input:

• Một số nguyên duy nhất ~k~ ~(1 \le k \le 10^{18})~.

Output:

• Một số nguyên là số chính phương không lặp lại lớn thứ ~k~. Nếu số này không tồn tại, in ra ~-1~.

Sample Input 1

9

Sample Output 1

81

Sample Input 2

10

Sample Output 1

169