#PU1443. USACO 2024 December Contest, Bronze — Problem 1. Roundabout Rounding

USACO 2024 December Contest, Bronze — Problem 1. Roundabout Rounding

USACO 2024 December Contest, Bronze — Problem 1. Roundabout Rounding

题目描述

Bessie the cow is back in school! She has started doing her math homework in which she is tasked to round positive integers to powers of 1010. To round a positive integer aa to the nearest 10b10^b, where bb is a positive integer, Bessie first locates the bb'th digit from the right. Let xx denote this digit. If x≥5x \geq 5, Bessie adds 10b10^b to aa. Then, Bessie sets all the digits including and to the right of the bb'th digit from the right to be 00. For instance, if Bessie wanted to round 456456 to the nearest 10210^2 (hundred), Bessie would first locate the 22nd digit from the right which is 55. This means x=5x = 5. Then since x≥5x \geq 5, Bessie adds 100100 to aa. Finally, Bessie sets all the digits in aa to the right of and including the 22nd digit from the right to be 00, resulting in 500500. However, if Bessie were to round 446446 to the nearest 10210^2, she would end up with 400400. After looking at Bessie's homework, Elsie thinks she has invented a new type of rounding: chain rounding. To chain round to the nearest 10b10^b, Elsie will first round to the nearest 10110^1, then the nearest 10210^2, and so on until the nearest 10b10^b. Bessie thinks Elsie is wrong, but is too busy with math homework to confirm her suspicions. She tasks you to count how many integers xx at least 22 and at most NN (1≤N≤1091 \leq N \leq 10^{9}) exist such that rounding xx to the nearest 10P10^P is different than chain rounding to the nearest 10P10^P, where PP is the smallest integer such that 10P≥x10^P \geq x.

输入格式

You have to answer multiple test cases. The first line of input contains a single integer TT (1≤T≤1051 \leq T \leq 10^5) denoting the number of test cases. TT test cases follow. The first and only line of input in every test case contains a single integer NN. All NN within the same input file are guaranteed to be distinct.

输出格式

(见题面原文)

数据范围

Inputs 2-4: N≤103N\le 10^3 Inputs 5-7: N≤106N\le 10^6 Inputs 8-13: No additional constraints. Problem credits: Weiming Zhou

样例

样例 1

4
1
100
4567
3366
0
5
183
60
Consider the second test case in the sample. $48$ should be counted because $48$
chain rounded to the nearest $10^2$ is $100$ ($48\to 50\to 100$), but $48$
rounded to the nearest $10^2$ is
$0$.
In the third test case, two integers counted are $48$ and $480$. $48$ chain 
rounds to $100$ instead of to $0$ and $480$ chain rounds to $1000$ instead of
$0$.  However, $67$ is not counted since it chain rounds to $100$ which is $67$
rounded to the nearest $10^2$.