Nico Number

Time Limit: 2 Seconds
Memory Limit: 262144 KB

*Kousaka Honoka* and *Minami Kotori* are playing a game about a secret of *Yazawa Nico*.

When the game starts,

*Kousaka Honoka* will give

*Minami Kotori* an array

`A` of

`N` non-negative integers. There is a special kind of number in the array, which is called

*NicoNico-number*. We call a integer

`x` is a

*NicoNico-number*, if all integers(no more than

`x`) that is coprime with

`x` could form an Arithmetic Sequence.

Then

*Minami Kotori* will choose some consecutive part of the array

`A`, wondering the number of

*NicoNico-number* in this part.
What's more,

*Kousaka Honoka* sometimes modify the value of some consecutive elements in the array. Now it is your task to simulate this game!

#### Input

There are multiple test cases in input, you should process to the end of file.

For each case, the first line is an integer `N`, the number of elements in the array described above.
Then second line contains `N` integers no greater than 10^{7}, the elements of the array initially.(`1 <= N <= 100,000`)

The third line is a integer `T`, the number of the operations of the game. Each line of the following `T` lines
is in one of the following formats.(`1 <= T <= 100,000`)

"1 L R" : *Minami Kotori* will chooses the consecutive part of the array from the `L`th to `R`th element inclusive.
(1 <= `L <= R` <= N)

"2 L R v" : *Kousaka Honoka* will change the value of the `p`th element `A[p]` in the array to `A[p]%v` for all `L <= p <= R`.(`1 <= L <= R <= N, 1 <= v <= 10`^{7})

"3 p x" : *Kousaka Honoka* will change the value of the `p` th element `A[p]` to `x`.(`1 <= p <= N, 1 <= x <= 10`^{7})

#### Output

Each time when *Minami Kotori* chooses some part of the array, you should output a line, the number of *NicoNico-number* in that part.

#### Sample Input

3
4 6 9
6
1 1 3
1 3 3
2 1 1 10
1 1 3
3 2 4
1 1 3

#### Sample Output

2
0
2
2

#### Hint

4 is a *NicoNico-number* because only 1 and 3 is coprime with 4 among the integers no greater than 4, and could form an Arithmetic Sequence {1,3}.

Author:

**ZHANG, Ruixiang**
Source:

**ZOJ Monthly, July 2015**
Submit
Status