페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
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

역링크 공식 문제집만