Trúc là một người cực kì yêu thích số 9. Lê Văn Tài aka Who you knows Who đã thích Trúc từ lâu và rủ Trúc cùng đi chơi Tết. Trúc biết Tài rất giỏi CNTT nên muốn thử thách Tài bài toán sau :

"Cho một số nguyên n, n<=10¹² hãy đưa ra số lượng số nguyên dương nhỏ hơn n có chính xác 9 ước số".

Trúc bảo Tài phải làm hết bài này mới chịu đi chơi Tết với Tài. Các bạn hãy giúp Tài với nhé.

Dữ liệu vào: 

• Dòng đầu tiên chứa số nguyên T(T<=10⁴ ) là số lượng test
• T dòng tiếp theo, mỗi dòng chưa một số nguyên dương n.

Dữ liệu ra:

• T dòng, mỗi dòng là kết quả của bài toán.

Ví dụ: