CNTPRIME - Counting Primes


Tortoise and Achilles are playing the Counting the Primes game. Achilles will give Tortoise some numbers, and some intervals, and then Tortoise needs to count the primes on those intervals. It is an easy game, but Tortoise is doing the counting slowly. Achilles is pissed off, so he has given you the task as you are a good programmer. For a twist, he has changed the game a little bit, that is he will give some intervals for counting the prime as well as he will give some intervals to change the numbers in that interval.

You are given an array of n elements. After that you will be given M commands. They are:

  • 0 x y v - you have to change all numbers in the range of x to y (inclusive) to v, where x and y are two indexes of the array.
  • 1 x y - output a line containing a single integer which is the number of primes between x and y (inclusive).

The array is indexed from 1 to n.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case contains two integers n (1 ≤ n ≤ 104) and q (1 ≤ q ≤ 2×104). Then next line, you will be given N integers. After that each of the next q lines will contain a task in one of the following form:

  • 0 x y v (1 ≤ x ≤ y ≤ n, 2 ≤ v ≤ 106)
  • 1 x y (1 ≤ x ≤ y ≤ n)

And the numbers will be in range of [2, 106].

Output

For each case, print the case number first. Then for each query '1 x y', print the number of primes between x and y [inclusively].

Example

Input:
1
5 3
78 2 13 12 3
1 1 2
0 4 4 5
1 1 5

Output:
Case 1:
1
4

Note:

  • Use Faster IO like scanf, printf
  • A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first prime numbers are 2, 3, 5, 7, 11 ...

hide comments
yurkoflisk: 2015-09-03 16:47:22

LOL. TLE with scanf/printf and AC with cin/cout(with ios_base::sync_with_stdio(false), cin.tie(nullptr) and using '\n' instead of endl)

hnvahidi: 2015-08-12 13:30:42

hey guys
passed using scnaf and printf :|
strict time limit
you're really making fun of us :|

Abhinandan Agarwal: 2015-08-03 18:51:08

Silly mistakes .. :-( ..

arjundabra: 2014-12-19 06:58:42

do we have to print case no.: for those cases in which no print query is asked???

Divyank Duvedi: 2014-12-03 08:08:19

very nice question.....strict time limits

Luis Manuel D�az Bar�n: 2014-11-08 09:01:43

Easy and beautiful problem, little bugs leaded me to 7 WAs. Finally AC

Akhilesh Anandh: 2014-11-04 18:41:38

Weak test cases... Wrote code which considers 1 as a prime number, got Accepted :P

Reply: Actually there are no cases where you will be given a value 1. Check the input constraint.

Last edit: 2014-11-14 23:58:07
Angel Gonzalez: 2014-10-24 01:35:19

Segment Tree + Sieve + Lazy Propagation = AC :)

mkrjn99: 2014-10-23 12:55:09

Take care of I/O format.It caused me 1 WA :-(

Aditya Pande: 2014-10-11 10:58:59

getting TLE even with lazy propagation and fast io

Last edit: 2014-10-11 11:54:21

Added by:Faiyaz
Date:2012-12-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem