# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Easy Prime!

Limits: 1s, 256 MB

There are **N** numbers in an array. You will have **Q** queries. In each query, you can make 2 operations. These are:

```
1 X Y . This will print total number of prime numbers in the range X & Y (inclusive).
2 X a . This will update the value at index X with the value a. If previous value at index X is b, then it will now be updated as a.
```

[1 based indexing]

### Input

In the first line take N as input, then in the next line take N numbers as input in your array. The next line of input will take Q. It indicates the total number of queries. Then next Q lines will contain the Queries.
**[1<=N<=10^5, 1<=Q<=10^5]** [Max value of Prime number is **10^7**]

### Output

For each input, print the total number of primes in the range **X** and **Y**. (inclusive)

### Samples

Input | Output |
---|---|

10 12 9 29 14 9 76 7 6 8 10 5 1 1 4 2 4 29 1 1 4 2 1 29 1 1 4 | 1 2 3 |

#### tahmedge

→