2023년이 기대되는 이유

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$이 아니다.