题目描述

给定一个正整数n，你需要将它表示为若干不同的完全平方数的和（注：完全平方数是指一个整数是另一个数的平方，如 1，4，9，16，25等均是完全平方数，换而言之，如果一个数能够表示成某个整数的平方形式，那么这个整数就是完全平方数）。请编写一个程序实现这一过程。例如，如果n=12，则可以表示为4+4+4或1+1+1+9，但是不能表示为11+1。

提示信息

本题可以采用贪心算法解决。先将所有小于或等于n的完全平方数存储的列表中，然后从大到小遍历这个列表，每次都选择最大的完全平方数，并将其从n中减去，直到n变成0

Samples

12

12=9+1+1+1

Limitation

1s, 1024KiB for each test case.