페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8176
서브태스크

반올림 방법 1초 1024MB

문제

한글이는 양의 정수 x10의 거듭제곱 10^P으로 반올림하는 두 가지 방식에 대해 고민하고 있다. P10^P \geq x를 만족하는 최소의 값이다.

  1. 일반 반올림: x를 가장 가까운 10^P으로 한 번에 반올림.

  2. 연쇄 반올림: x10^1, 10^2, ..., 10^P 순서로 반복해서 반올림.

예를 들어 x=546인 경우를 생각해보면 P3이 된다. 다음 두 반올림 방법은 아래와 같이 진행된다.

  • 일반 반올림: 546 \to 1000
    x10^3으로 바로 반올림. 세 번째 자릿수 55 이하이므로 1000을 얻음.

  • 연쇄 반올림: 546 \to 550 \to 600 \to 1000
    10^1으로 먼저 반올림해 550을 얻은 후, 10^2으로 다시 반올림해 600을 얻고, 10^3으로 다시 반올림하여 1000을 얻음.

  • 결과: 두 방식 모두 동일.

다른 케이스인 x=449인 경우도 P3이 되고, 아래와 같이 진행된다.

  • 일반 반올림: 449 \to 0
    x10^3으로 바로 반올림. 세 번째 자릿수 45 이하이므로 0을 얻음.

  • 연쇄 반올림: 449 \to 450 \to 500 \to 1000
    10^1으로 먼저 반올림해 450를 얻은 후, 10^2으로 다시 반올림해 500을 얻고, 10^3으로 다시 반올림하여 1000을 얻음.

  • 결과: 두 방식이 다름.

한글이는 1 \leq x \leq N 범위에서 두 방식의 결과가 다른 정수의 개수를 세고 싶다. 여기서 N1 \leq N \leq 10^9을 만족한다.


입력

여러 개의 테스트 케이스를 처리해야 한다.

  • 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 T(1 ≤ T ≤ 100,000)이 주어집니다. T개의 테스트 케이스가 뒤따른다.

  • 각 테스트 케이스의 첫 번째이자 유일한 줄에는 정수 N이 주어집니다. 같은 입력 파일 내의 모든 N은 서로 다른 값임이 보장된다.


출력

T개의 줄을 출력하며, i번째 줄에는 i번째 테스트 케이스에 대한 답을 나타내는 정수를 출력한다.

각 줄은 두 반올림 방법을 사용했을 때 결과가 다른 2 ≤ x ≤ N 범위 내의 정수의 개수를 나타내는 정수여야 한다.


부분문제

번호 점수 조건
#120점

N≤10^3

#230점

N≤10^4

#350점

추가 제약 조건 없음


예제1

입력
4
1
100
4567
3366
출력
0
5
183
60

두 번째 테스트 케이스에서, 48과 같은 수들이 카운트된다. 48을 연쇄 반올림하여 가장 가까운 10^2으로 반올림하면 100이 된다 (4850100), 하지만 48을 일반 반올림하여 가장 가까운 10^2로 반올림하면 0이 된다.

세 번째 테스트 케이스에서는 48480 등이 카운트된다.

  • 48은 연쇄 반올림을 통해 100으로 반올림되지만, 일반 반올림에서는 0이 된다.

  • 480은 연쇄 반올림을 통해 1000으로 반올림되지만, 일반 반올림에서는 0이 된다.

하지만 67은 카운트되지 않는다. 67은 연쇄 반올림으로도 100(6770100)이 되고, 일반 반올림으로도 100이 되기 때문이다.


출처

USACO 2024 December Bronze

역링크