Bessie đã quay lại trường học! Cô bắt đầu làm bài tập toán, trong đó cô được yêu cầu làm tròn các số nguyên dương đến các lũy thừa của \(10\).

Để làm tròn một số nguyên dương \(a\) đến \(10^b\) gần nhất, với \(b\) là một số nguyên dương, trước tiên Bessie tìm chữ số thứ \(b\) tính từ bên phải. Gọi chữ số này là \(x\).

Nếu \(x \geq 5\), Bessie cộng \(10^b\) vào \(a\).

Sau đó, Bessie đặt tất cả các chữ số từ chữ số thứ \(b\) tính từ bên phải trở về bên phải, kể cả chữ số đó, thành \(0\).

Ví dụ, nếu Bessie muốn làm tròn \(456\) đến \(10^2\) (hàng trăm) gần nhất, trước tiên cô tìm chữ số thứ \(2\) tính từ bên phải là \(5\). Do đó \(x=5\). Vì \(x\geq 5\), Bessie cộng \(100\) vào \(a\). Cuối cùng, cô đặt chữ số thứ \(2\) tính từ bên phải và tất cả các chữ số bên phải nó trong \(a\) thành \(0\), thu được \(500\).

Tuy nhiên, nếu Bessie làm tròn \(446\) đến \(10^2\) gần nhất, kết quả sẽ là \(400\).

Sau khi xem bài tập của Bessie, Elsie cho rằng mình đã phát minh ra một kiểu làm tròn mới: làm tròn dây chuyền. Để làm tròn dây chuyền đến \(10^b\) gần nhất, trước tiên Elsie làm tròn đến \(10^1\) gần nhất, sau đó đến \(10^2\) gần nhất, và tiếp tục như vậy cho đến \(10^b\) gần nhất.

Bessie nghĩ Elsie đã sai, nhưng quá bận làm bài tập toán để xác nhận nghi ngờ của mình. Cô giao cho bạn đếm số lượng số nguyên \(x\) từ \(2\) đến \(N\) (\(1\leq N\leq 10^9\)) sao cho làm tròn \(x\) đến \(10^P\) gần nhất khác với làm tròn dây chuyền đến \(10^P\) gần nhất, trong đó \(P\) là số nguyên nhỏ nhất thỏa mãn \(10^P\geq x\).

Dữ liệu vào

Bạn phải trả lời nhiều bộ test.

Dòng đầu chứa một số nguyên \(T\) (\(1\leq T\leq 10^5\)), là số bộ test. Tiếp theo là \(T\) bộ test.

Dòng duy nhất của mỗi bộ test chứa một số nguyên \(N\). Tất cả các giá trị \(N\) trong cùng một tệp đầu vào được đảm bảo đôi một khác nhau.

Dữ liệu ra

In ra \(T\) dòng, dòng thứ \(i\) chứa đáp án cho bộ test thứ \(i\). Mỗi dòng là một số nguyên biểu thị số lượng số nguyên từ \(2\) đến \(N\) cho kết quả khác nhau khi dùng hai phương pháp làm tròn.

Phân nhóm

• Các test 2–4: \(N\leq 10^3\).
• Các test 5–7: \(N\leq 10^6\).
• Các test 8–13: Không có ràng buộc bổ sung.

Ví dụ

4
1
100
4567
3366

0
5
183
60

Nguồn

Đề bài gốc: USACO 2024 December Contest, Bronze — Roundabout Rounding

Tác giả: Weiming Zhou.