1328: C - 塔子哥的水题

塔子哥有一排连续的自然数摆在面前，例如下面所示:

$1\ 2\ 3\ 4\ 5\ 6\ 7$

他认为质数是非常让人头疼的数(质数定义:除了1和它本身外，没有其他约数的数)

所以他会将里面所有质数一个一个划掉,之后将剩下的数重新编号，过程如下图所示:

$1\ (2)\ (3)\ 4\ (5)\ 6\ (7)\ \underset{删除质数}{\rightarrow} 1\ 4\ 6  \underset{重新编号}{\rightarrow} 1\ 2\ 3$  

我们称该过程为一次迭代。

现在给你$n$个数排成一排,塔子哥想知道经过$k$轮迭代之后数组中还剩多少个数。

第一行给定一个数$T$,代表测试组数。

接下来$T$行,每行两个数$n\ k$, 含义如题目所示，用空格隔开.

输出$T$行,每一行一个整数,代表对应的$n\ k$ 条件下，最后剩的数的个数。

3
7 0
7 1
7 3

7
3
1

## 样例解释

$k=0,$

$数组状态为:1\ 2\ 3\ 4\ 5\ 6\ 7,此时还剩7个数$



$k=1,$

$迭代:1\ (2)\ (3)\ 4\ (5)\ 6\ (7)\ \underset{删除质数}{\rightarrow} 1\ 4\ 6  \underset{重新编号}{\rightarrow} 1\ 2\ 3$  

$数组状态为:1\ 2\ 3,此时还剩3个数$



$k=2$,

$迭代:1\ (2)\ (3)\ \underset{删除质数}{\rightarrow} 1 \underset{重新编号}{\rightarrow} 1$  

$数组状态为:1,此时还剩1个数$



$k=3$,

$迭代:1\ \underset{删除质数}{\rightarrow} 1 \underset{重新编号}{\rightarrow} 1$  

$数组状态为:1,此时还剩1个数$



## 数据范围

$10\%$的数据:$T=1,n = 20,k=3$            

$20\%$的数据:$T=1,n \leq 1000,k = 1$     

$10\%$的数据:$T=5,n \leq 10000,k \leq 1000$     

$20\%$的数据:$T=10,n \leq 100000,k \leq 1000$      

$20\%$的数据:$T\leq 50,n \leq 200000,k \leq 1000$   

$10\%$的数据:$T\leq500000,n \leq 500000,k \leq 100000000000$  

$10\%$的数据:$T\leq3000000,n \leq 3000000,k \leq 100000000000$