Description

$197$ 被称之为循环质数，因为所有的轮换： $197$ ， $971$ 和 $719$ 都是质数。

有 $13$ 个数字小于等于 $100$ ： $2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79,$ 和 $97$ 。

输入 $n$ ，求有多少个循环质数小于等于 $n$ ？

Input Format

输入第一行组数 $T$ ， 接下来 $T$ 行，每行一个整数 $n$ 。 $(1 \le T \le 110)$ $(1 \le n \le 1000000)$

Output Format

对于每组数据，输出一个数，表示循环质数小于等于 $n$ 的个数。

2
100
1000000

13
55