케이크
시간 제한30초메모리 제한1024 MB
한 변의 길이가 정수인 정사각형 케이크의 넓이 합이 정확히 N이 되도록 하면서 케이크 개수를 최소로 하는 값을 구한다.
문제
Wheatley는 세상에서 가장 멋진 파티에 왔다. 이 파티에는 케이크가 무한히 많다! 각 케이크는 한 변의 길이가 정수인 정사각형이다(단위는 cm). 파티에는 가능한 모든 정수 변 길이의 케이크가 무한히 있다. 모든 케이크의 높이는 같으므로 넓이만 생각한다.
Wheatley는 넓이의 합이 정확히 N cm2인 케이크를 하나 이상 먹기로 마음먹었다. 하지만 건강을 생각하는 그는 케이크를 최대한 적게 먹고 싶어 한다. 그가 먹을 수 있는 케이크 개수의 최솟값을 구할 수 있겠는가?
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, Wheatley가 먹으려는 케이크 넓이의 정확한 합 N이 하나 주어진다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 넓이의 합이 정확히 N이 되도록 Wheatley가 먹을 수 있는 케이크 개수의 최솟값이다.
힌트
예제 1에서는 한 변의 길이가 1인 케이크 세 개를 먹는 방법밖에 없다.
예제 2에서는 한 변의 길이가 2인 케이크 하나를 먹을 수 있고, 이는 한 변의 길이가 1인 케이크 네 개를 먹는 것보다 개수가 적다.
예제 3에서는 한 변의 길이가 2인 케이크 하나와 한 변의 길이가 1인 케이크 하나를 먹는 것이 최선이다.