Cho số nguyên dương ~n~ (~n~ ~\le~ ~10^{18}~), hãy đưa ra số lượng các số từ ~1~ đến ~n~, thoả mãn số đó không chia hết cho bất kỳ số nào trong các số từ ~2~ đến ~10~

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~t~ ~\le~ ~10^5~) là số test của đề bài

~t~ dòng tiếp theo, mỗi dòng chứa số nguyên dương ~n~ (~n~ ~\le~ ~10^{18}~)

OUTPUT

Đưa ra ~t~ dòng, mỗi dòng một số nguyên, là số các số từ ~1~ đến ~n~, thoả mãn số đó không chia hết cho bất kỳ số nào trong các số từ ~2~ đến ~10~

SAMPLE INPUT

1
12

SAMPLE OUTPUT

2