Let *D*(*x*) be the number of positive divisors of a positive integer *x*. For example, *D*(2) = 2 (2 is divisible by 1 and 2), *D*(6) = 4 (6 is divisible by 1, 2, 3 and 6).

You are given an array *a* of *n* integers. You have to process two types of queries:
 1.  REPLACE *l* *r* — for every <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/6afb5e3d414ffbb040c175e23c6627da949add06.png" style="max-width: 100.0%;max-height: 100.0%;"/> replace *a*<sub class="lower-index">*i*</sub> with *D*(*a*<sub class="lower-index">*i*</sub>); 1.  SUM *l* *r* — calculate <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/1e50b9417bb7e50d92d43134922596e938249431.png" style="max-width: 100.0%;max-height: 100.0%;"/>. 
Print the answer for each SUM query.
The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 3·10<sup class="upper-index">5</sup>) — the number of elements in the array and the number of queries to process, respectively.

The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">6</sup>) — the elements of the array.

Then *m* lines follow, each containing 3 integers *t*<sub class="lower-index">*i*</sub>, *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> denoting *i*-th query. If *t*<sub class="lower-index">*i*</sub> = 1, then *i*-th query is REPLACE *l*<sub class="lower-index">*i*</sub> *r*<sub class="lower-index">*i*</sub>, otherwise it's SUM *l*<sub class="lower-index">*i*</sub> *r*<sub class="lower-index">*i*</sub> (1 ≤ *t*<sub class="lower-index">*i*</sub> ≤ 2, 1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*).

There is at least one SUM query.
none
7 6
6 4 1 10 3 2 4
2 1 7
2 4 5
1 3 5
2 4 4
1 5 7
2 1 7
30
13
4
22
4 2
1 1 1 3
1 1 4
2 1 4
5
10 2
1 1 1 1 1 1 1 1 1 9
1 1 10
2 1 10
12
4 2
1 1 3 1
1 1 4
2 1 4
5
5 3
1 1 1 1 3
2 1 5
1 1 5
2 1 5
7
6
7 10
1 1 1 1 1 1 1
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
2 1 7
7
class Node:
    def __init__(self,start,end):
        self.start=start
        self.end = end
        self.left = None
        self.right = None
        self.val = 0
        
class SegmentTree:
    def __init__(self,arr):
        self.arr = arr
        self.root = self.build(0,n-1)
        
    def build(self,start,end):
        if start>end:
            return 
        node = Node(start,end)
        
        if start==end:
            node.val = self.arr[start]
            return node
        
        mid = (start+end)//2
        
        node.left = self.build(start,mid)
        node.right = self.build(mid+1,end)
        
        node.val = node.left.val+node.right.val
        
        return node
    
    def getSum(self,node,low,high):
        start = node.start
        end = node.end
        
        if low>end or high<start:
            return 0
        
        if low<=start and high>=end:
            return node.val
        
        return self.getSum(node.left,low,high)+self.getSum(node.right,low,high)

    def update(self,node,low,high):
        if low>node.end or high<node.start:
            return
        
        if node.start == node.end:
            node.val = self.getCount(node.val)
            
            return
        
        self.update(node.left,low,high)
        self.update(node.right,low,high)
        
        node.val = node.left.val+node.right.val
        return
    def getCount(self,val):
        from math import sqrt
        from math import ceil
        if val == 1:
            return 1
        if val == 2:
            return 2
        
        if val == 3:
            return 2
        count = 0
        for i in range(1,ceil(sqrt(val))+1):
            #print(i)
            if val%i == 0:
                # print(i,val)
                if i!=sqrt(val):
                    count += 2
                else:
                    count += 1
        return count
        
n,q = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
tree = SegmentTree(arr)

for i in range(q):
    t,l,r = [int(x) for x in input().split()]
    if t == 1:
        
        tree.update(tree.root, l-1,r-1)
        #print(tree.arr)
    else:
        print(tree.getSum(tree.root,l-1,r-1))