시간 제한메모리 제한제출정답맞힌 사람정답 비율
2.9 초 329 MB52493291.429%

문제

루미는 수미상관 수에 대해 알게 되었다. 수미상관 수의 정의는 다음과 같다.

  • 양의 정수 $n$을 십진수로 썼을 때의 길이가 $k$일 때, 앞쪽 $\left\lfloor \frac{k}{2} \right\rfloor$ 자리가 뒤쪽 $\left\lfloor \frac{k}{2} \right\rfloor$자리와 정확히 같으면 $n$을 수미상관 수라고 한다.

예를 들어, 1, 1111, 707, 12312는 수미상관 수이고, 10, 12321은 수미상관 수가 아니다.

루미는 문득 임의의 양의 정수를 두 수미상관 수의 합으로 나타낼 수 있는지 궁금해졌다. 루미를 위해, 양의 정수가 주어졌을 때 두 수미상관 수의 합으로 나타내는 방법의 수를 구해 보자. 서로 다른 두 수의 순서를 바꾼 것은 서로 다른 것으로 센다.

입력

입력의 첫 줄에는 테스트 케이스의 수 $T$가 주어진다.

두 번째 줄부터 $T$줄에 걸쳐서 양의 정수 $N$이 한 줄에 하나씩 주어진다.

출력

각 테스트 케이스에 대해, $N$을 두 수미상관 수의 합으로 나타내는 방법의 수를 한 줄에 출력한다.

제한

  • $1\le T\le 10$
  • $1\le N\le 10^9$

예제 입력 1

3
10
12345
999999999

예제 출력 1

9
6
80000

출처

Contest > BOJ User Contest > Happy Birthday Lumi! > Happy Birthday Lumi! 2026 E번