Card Collection Prime Query

You are given a collection of cards, each card having an integer value. Initially, there are N cards with given values. You will be asked to process M queries. There are two types of queries:

• Update Query (type 1): Update the card at position i to a new value x.
• Count Query (type 2): Count how many cards within the range [L, R] (inclusive) have prime numbers as their values.
</p>

Recall that a prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. In terms of a formula, a number \(p\) is prime if it satisfies \[ p > 1 \quad \text{and} \quad \nexists\ d \in \mathbb{Z},\ 2 \le d \le \sqrt{p} \quad \text{such that} \quad d\,|\,p. \]

You need to answer all count queries according to the updates as they occur.

inputFormat

The input is given from stdin and is formatted as follows:

N
v1 v2 ... vN
M
query1
query2
...
queryM

Here, N is the number of cards. The second line contains N integers representing the initial card values. M is the number of queries. Each query is represented by three integers separated by spaces. For an update query, the line is "1 i x" meaning update the i-th card to x. For a count query, the line is "2 L R" meaning count the number of prime numbers in the range from index L to R (inclusive).

outputFormat

For each count query (type 2), output a single line with the number of prime valued cards in the specified range. The output should be printed to stdout.

## sample

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

1
3

</p>