26036번 - 제곱 ㄱㄱ 스페셜 저지

BOJ의 쉬운 문제 제곱 ㄴㄴ를 풀지 못해 화가 난 명준은 제곱ㄴㄴ수를 뒤집은 제곱ㄱㄱ수를 만들어냈다.

양의 정수 X의 모든 소인수 p에 대하여 p²도 X의 약수라면, X를 제곱ㄱㄱ수라고 한다. 첫 제곱ㄱㄱ수는 1, 4, 8, 9, 16, 25, 27, 32, ... 이다.

제곱ㄱㄱ수를 하나 찾아내는 것은 쉽다. 아무 거듭제곱수를 잡으면 곧 제곱ㄱㄱ수이기 때문이다. 또 명준은 모든 제곱ㄱㄱ수는 제곱수와 세제곱수를 곱한 형태로 표현할 수 있다는 것도 알아냈다.

원하는 크기의 제곱ㄱㄱ수 하나를 찾는 것이 쉽기 때문에, 명준은 이웃한 두 양의 정수가 모두 제곱ㄱㄱ수가 되는 경우를 찾으려고 한다. 명준이 원하는 크기의 이웃한 두 제곱ㄱㄱ수가 있는지 찾아주자!

첫째 줄에 정수 N이 주어진다. (0 ≤ N < 1000)

A와 A+1 가 모두 제곱ㄱㄱ수이고, 100^N ≤ A < 100^N+1 을 만족하는 A를 찾으면 된다.

조건을 만족하는 A가 존재하는 경우, 첫째 줄에 A = B²C³ 인 두 양의 정수 B, C를 출력한다.

이어서 둘째 줄에 A + 1 = D²E³ 인 두 양의 정수 D, E를 출력한다.

조건을 만족하는 A가 여럿 있다면 그 중 하나에 대한 답만을 출력한다.

조건을 만족하는 A가 없는 경우에는 첫째 줄에 -1을 출력하고 종료한다.