35030번 - 2026년이 기대되는 이유

문제

Good Bye, BOJ 2025! 대회는 2025년을 마무리하며 2026년의 시작을 기념하는 알고리즘 문제해결 대회이다.

다들 저마다의 이유로 2026년을 기대하고 있겠지만, 위대한 수학자 준겸이는 남들과 조금 다른 방식으로 기대하고 있는 것 같다. 준겸이에 의하면, 2026이라는 수는 아래의 네 가지 수가 모두 소수이기 때문에 2026년은 특별한 한 해가 될 것이라고 한다.

• 2026ドル+1=2027$
• 2ドル\times 026+1=53$
• 20ドル\times 26+1=521$
• 202ドル\times 6+1=1213$

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

10진법으로 표기된 양의 정수 $n=\overline{d_1d_2\cdots d_k}$이 있을 때, 만약 $n+1$이 소수이고, 모든 1ドル\le i\le k-1$에 대해 $\overline{d_1\cdots d_i}\times\overline{d_{i+1}\cdots d_k} +1$이 소수라면 $n$을 특별한 수라고 하자.

양의 정수 $N$이 주어지면 $N$보다 작거나 같은 양의 정수 중 특별한 수의 개수를 세는 문제를 풀어보자.

입력

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

이후 $T$개의 줄에 걸쳐, 양의 정수 $N$이 한 줄에 하나씩 주어진다.

출력

각 테스트 케이스에 대해, $N$보다 작거나 같은 양의 정수 중 특별한 수의 개수를 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• 1ドル\le T\le 100,円 000$
• 1ドル\le N\le 100,円 000$

노트