nguồn đề : https://www.spoj.com/problems/VECTAR8/

A và B rất sợ các số nguyên tố, nhưng họ không phải sợ tất cả các số nguyên tố, họ chỉ sợ một các số tố thỏa mãn hai yếu tố sau :

• Không chứa chữ số '0'.
• Không quan trọng bỏ bao nhiêu chữ số ở đầu đầu, số còn lại vẫn là số nguyên tố. Ví dụ một số nguyên tố mà A và B sợ là 4632647 vì nó không chứa kí tự 0 và tập tất các số sau khi bỏ đi một số chữ cái đầu đều là số nguyên tố (4632647, 632647, 32647, 2647, 647, 47, 7).

Cho một số N hãy in ra số lượng số nguyên tố không lớn hơn N mà A và B sợ.

Input

Dòng đầu tiên chứa 1 số nguyên t ~(1 \le t \le 10^5)~

t dòng tiếp theo mỗi dòng chứa 1 số nguyên n ~(1 \le n \le 10^6)~

Output

Với mỗi số n in ra số lượng số nguyên tố không lớn hơn n mà A và B sợ.

Sample Input 1

3
2
3
4

Sample Output 1

1
2
2