Description

我们定义一种特殊的数：如果这个数本身是素数，并且去掉它的最后一位数字后剩下的部分仍然是素数（或为空），则称其为“前缀素数”。例如： 素数 293是前缀素数，因为：

293是素数,

去掉末位得 29，是素数,

再去掉末位得 2，是素数,

最后剩下空，停止。

给定一个整数 N(1≤N≤1e6)，请计算区间 [1,N]内有多少个前缀素数。

Format

Input

第一行包含一个整数 T(1≤T≤10)，表示测试用例的数量。

接下来 T行，每行包含一个整数 N。

Output

对于每个测试用例，输出一行，包含一个整数，表示区间 [1,N]内前缀素数的个数。

Samples

3
10
50
1000

4
8
27

Limitation

1s, 256MB for each test case.