시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB74128622941.261%

문제

Hello, BOJ 2023! 대회는 2023년의 시작을 기념하는 알고리즘 문제해결 대회이다.

다들 저마다의 이유로 올 한 해를 기대하고 있겠지만, Good Bye, BOJ 2022!와 Hello, BOJ 2023! 두 대회의 운영진들은 대회장에서 참가자 여러분을 만날 수 있게 되어 감사한 마음으로 2023년을 한껏 기대하고 있다.

하지만 위대한 수학자 준겸이는 2023년을 조금 다른 방식으로도 기대하고 있는 것 같다. 준겸이에 의하면, 2023이라는 수는 다음의 두 등식:

  • $2^1+0^1+2^1+3^1=2+0+2+3$
  • $2^3+0^3+2^3+3^3=20+23$

을 동시에 만족하기 때문에, 올해도 좋은 해가 될 것이라고 한다.

여러분은 이 얘기를 듣고, 다른 연도에 대해서도 준겸이가 말한 좋은 성질이 성립하는지가 궁금해졌다.

$10$진법으로 표기된 양의 정수 $n=\overline{d_0d_1\cdots d_k}$ 가 주어진다. $n$의 자릿수 사이사이에 $0$개 이상의 $+$ 기호를 넣어서 계산했을 때, 그 값이 $d_0^m+d_1^m+\cdots +d_k^m$ 과 같아지도록 하는 양의 정수 $m$의 개수를 구하면 된다.

$+$ 기호를 삽입하는 방법의 수가 아닌, $m$의 개수를 구해야 함에 유의하여라.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

이후 $T$개의 줄에 걸쳐 $10$진법으로 표현된 양의 정수 $n$이 주어진다.

출력

각 테스트 케이스에 대해, $m$의 개수를 출력하여라.

만약 그러한 $m$이 무수히 많다면, Hello, BOJ 2023!을 출력한다.

제한

  • $1\leq T\leq 1\, 000$
  • $1\leq n\leq 10^9$
  • 입력으로 주어지는 $n$의 가장 큰 자리 수는 $0$이 아니다.

예제 입력 1

5
1
9
2022
2023
1000000000

예제 출력 1

Hello, BOJ 2023!
1
2
2
Hello, BOJ 2023!

$n = 1$의 경우, 모든 양의 정수 $m$에 대해서 $1^m = 1$이 성립하므로, 조건을 만족하는 $m$은 무수히 많다. 따라서 Hello, BOJ 2023!을 출력한다.

$n = 2022$의 경우, 

  • $2^1 + 0^1 + 2^1 + 2^1 = 2 + 0 + 2 + 2$
  • $2^3 + 0^3 + 2^3 + 2^3 = 2 + 0 + 22$

이므로, 가능한 $m$의 개수는 $2$개이다. 따라서 $2$를 출력한다.

출처

Contest > BOJ User Contest > Good Bye, BOJ > Hello, BOJ 2023! A번