케이크

Wheatley는 세상에서 가장 멋진 파티에 와 있다. 이 파티에는 케이크가 무한히 많다! 각 케이크는 한 변의 길이(cm)가 정수인 정사각형이다. 파티에는 가능한 모든 정수 한 변 길이에 대해 케이크가 무한히 많이 있다. 모든 케이크의 깊이는 같으므로 넓이만 고려한다.

Wheatley는 넓이의 합이 정확히 N $cm^{2}$가 되도록 하나 이상의 케이크를 먹기로 결심했다. 하지만 건강을 신경 쓰기 때문에 가능한 한 적은 수의 케이크를 먹고 싶어 한다. Wheatley가 먹을 수 있는 케이크의 최소 개수를 계산하도록 도와줄 수 있는가?

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ T ≤ 50. 1 ≤ N ≤ 50.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ T ≤ 100. 1 ≤ N ≤ 10000.

입력은 테스트 케이스의 수를 나타내는 정수 T 하나를 포함하는 한 줄로 시작한다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 Wheatley가 먹고자 하는 정확한 케이크 넓이의 합을 나타내는 정수 N 하나가 있는 한 줄로 이루어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 정확히 넓이의 합 N만큼 먹으면서 Wheatley가 먹을 수 있는 케이크의 최소 개수이다.

예제 케이스 #1에서 가능한 유일한 전략은 Wheatley가 한 변의 길이가 1인 케이크 세 개를 먹는 것이다.

예제 케이스 #2에서 Wheatley는 한 변의 길이가 2인 케이크 하나를 먹을 수 있으며, 이는 한 변의 길이가 1인 케이크 네 개를 먹는 것보다 더 적은 수의 케이크를 필요로 한다.

예제 케이스 #3에서 최선의 전략은 Wheatley가 한 변의 길이가 2인 케이크 하나와 한 변의 길이가 1인 케이크 하나를 먹는 것이다.