You are given an array ~a~ of length ~N~, and ~Q~ queries, of the following forms:

• 1 l r Output the number of cancer integers in the subarray ~[l, r]~ ~(1 \le l \le r \le N)~.
• 2 i v Change the element at position ~i~ to be of value ~v~ ~(1 \le i \le N, 1 \le v \le 10^9)~.

We define a cancer integer as an integer with exactly 3 divisors.

Input Specification

The first line will contain two integers, ~N, Q~ ~(1 \le N,Q \le 10^5)~.

The second line will contain ~N~ space-separated integers ~a_1, a_2, a_3, \ldots, a_N~ ~(1 \le a_i \le 10^9)~, the initial array.

The next ~Q~ lines will each contain a valid query as defined above.

Output Specifcation

For each type ~1~ query, output the number of cancer integers in the subarray ~[l, r]~, on its own line.

Sample Input

5 4
2 4 5 1 25
1 1 4
2 2 3
1 1 2
1 3 5

Sample Output

1
0
1