문제
임의의 자연수는 제곱수의 합으로 나타낼 수 있다.
예를 들어 4 = 22, 5 = 22 + 12, 13 = 22 + 32 등 이다.
13 은 22 + 22 + 22 + 12으로도 나타낼 수 있지만 13 = 22 + 32 로 나타낼 때,
가장 적은 개수의 제곱수를 사용한다.
정수 N을 가능한 적은 개수의 제곱수의 합으로 나타내고자 한다.
이때 사용된 제곱수의 최소 개수를 출력하는 프로그램을 작성하시오.
입력
첫 행에 테스트 케이스의 수 T가 입력된다. (5 <= T <= 20)
다음 T개의 행에 Ni이 입력된다. (1 <= Ni <= 10,000,000,000)
출력
각 테스트 케이스에 대하여 사용된 제곱수의 최소 개수를 행으로 구분하여 출력한다.
예제
5
1
2
3
4
5
1
2
3
1
2
태그
출처
comkiwer
로그인해야 코드를 작성할 수 있어요.