Làm Tròn Vòng Vòng

Bessie làm tròn các số nguyên dương đến lũy thừa của $10$ theo quy trình sau: xác định chữ số thứ $b$ tính từ phải (gọi là $x$). Nếu $x\ge 5$, cộng thêm ${10}^b$ vào số. Sau đó đặt tất cả các chữ số ở vị trí $b$ và bên phải nó bằng $0$.

Elsie giới thiệu cách "làm tròn dây chuyền": lần lượt làm tròn đến ${10}^1$, rồi ${10}^2$, tiếp tục cho đến ${10}^b$.

Cho số nguyên $N$, đếm số lượng số nguyên từ $2$ đến $N$ mà kết quả làm tròn trực tiếp đến ${10}^P$ khác với kết quả làm tròn dây chuyền đến ${10}^P$, trong đó $P$ là số nguyên nhỏ nhất sao cho ${10}^P\ge x$.

Dữ liệu vào

• Dòng đầu: số nguyên $T$ ($1\le T\le {10}^5$) là số test case.
• Mỗi test case chứa một số nguyên $N$ ($1\le N\le {10}^9$).

Dữ liệu ra

Với mỗi test case, in ra một số nguyên - số lượng số từ $2$ đến $N$ mà hai cách làm tròn cho kết quả khác nhau.

Ràng buộc

• Test $2$-$4$: $N\le {10}^3$
• Test $5$-$7$: $N\le {10}^6$
• Test $8$-$13$: Không có ràng buộc thêm

Ví dụ