HTA 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 HTA từ lâu và rủ HTA cùng đi chơi Tết. HTA 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 \le 10^{12})~. Hãy đưa ra số lượng số nguyên dương nhỏ hơn hoặc bằng ~n~ có chính xác ~9~ ước số"

HTA 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é.

Input

• Dòng đầu tiên chứa số nguyên ~T~ ~(T \le 10^4)~ 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~.

Output

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

Ví dụ

Input

1 100

Output

2