write a go solution for Description:
Li Hua wants to solve a problem about varphi — Euler's totient function. Please recall that varphi(x)=sumlimits_i=1^x[gcd(i,x)=1].^dagger,ddagger

He has a sequence a_1,a_2,*s,a_n and he wants to perform m operations:

- "1 l r" (1<=l<=r<=n) — for each xin[l,r], change a_x into varphi(a_x).
- "2 l r" (1<=l<=r<=n) — find out the minimum changes needed to make sure a_l=a_l+1=*s=a_r. In each change, he chooses one xin[l,r], change a_x into varphi(a_x). Each operation of this type is independent, which means the array doesn't actually change.

Suppose you were Li Hua, please solve this problem.

^dagger gcd(x,y) denotes the greatest common divisor (GCD) of integers x and y.

^ddagger The notation [textrmcond] equals 1 if the condition textrmcond is true, and 0 otherwise.

Input Format:
The first line contains two integers n and m (1<=n,m<=10^5) — the number of elements in the array and the number of operations to process, respectively.

The second line contains n integers a_1,a_2,*s,a_n (1<=a_i<=5*10^6) — the elements of the array.

Next m lines, each line contains three integers t_i,l_i,r_i (t_iin1,2,1<=l_i<=r_i<=n) — the i-th operation.

Output Format:
For each "2 l r", output the answer in an separate line.

Note:
Denote varphi^k(x)=begincasesx,&k=0varphi(varphi^k-1(x)),&k>0endcases.

At first, a=[8,1,6,3,7].

To make sure a_1=a_2=a_3=a_4=a_5, we can change a to a'=[varphi^3(8),varphi^0(1),varphi^2(6),varphi^2(3),varphi^3(7)]=[1,1,1,1,1], using 3+0+2+2+3=10 changes.

To make sure a_3=a_4, we can change a to a'=[varphi^0(8),varphi^0(1),varphi^1(6),varphi^1(3),varphi^0(7)]=[8,1,2,2,7], using 0+0+1+1+0=2 changes.

After "1 1 3", a is changed to a=[varphi^1(8),varphi^1(1),varphi^1(6),varphi^0(3),varphi^0(7)]=[4,1,2,3,7].

To make sure a_3=a_4, we can change a to a'=[varphi^0(4),varphi^0(1),varphi^0(2),varphi^1(3),varphi^0(7)]=[4,1,2,2,7], using 0+0+0+1+0=1 change.. Output only the code with no comments, explanation, or additional text.