题目描述

给定一个N表示一个a1,a2,....,an的数组，给定M个查询由i到j，求从i到j有多少个质数（i，j为数组的下标）。

输入描述

第一行是一个整数t

下面有t组测试样例

然后下面一行有两个数N和M

下面一行有N个数和M次查询

下面有M行每行两个整数i,j.

输出描述

对于每组测试样例你应该先输出一个Case t: ，然后对与每个查询，你应该输出从i到j有多少个质数。

样例输入

1
8 4
1 2 3 4 5 6 7 8
1 3
2 5
3 6
4 4

样例输出

Case 1:
2
3
2
0

数据范围

$1<=t<=10,(1 <= N <= 10^5,1 <= M <= 50000,1 <= i <= j <= N$

题目来源

sz