B'Li Hua wants to solve a problem about varphi -- Euler 's totient function. Please recall that varphi(x)= sum limits_{i=1}^x[ gcd(i,x)=1] . ^{ dagger, ddagger} He has a sequence a_1,a_2, cdots,a_n and he wants to perform m operations: 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 [ textrm{cond}] equals 1 if the condition textrm{cond} is true, and 0 otherwise. 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}, cdots ,a_{n} ( 1 <= a_{i} <= 5 cdot 10^{6} ) -- the elements of the array. Next m lines, each line contains three integers t_{i},l_{i},r_{i} ( t_i in {1,2 },1 <= l_i <= r_i <= n ) -- the i -th operation. For each "2 l r ", output the answer in an separate line. Denote varphi^k(x)= begin{cases}x,&k=0 varphi( varphi^{k-1}(x)),&k > 0 end{cases} . 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. '...