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
import os, sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

sys.setrecursionlimit(2 ** 16)

# code starts here

class SegmentTree:
    tot = [] # interval sum
    val = [] # maximum value

    def __init__(self, n):
        self.tot = [0] * (n * 4)
        self.val = [0] * (n * 4)
        self.size = n

    def build(self, a, i, l, r):
        if l == r:
            self.tot[i] = self.val[i] = a[l - 1]
            return
        m = (l + r) >> 1
        self.build(a, i << 1, l, m)
        self.build(a, i << 1 | 1, m + 1, r)
        self.tot[i] = self.tot[i << 1] + self.tot[i << 1 | 1]
        self.val[i] = max(self.val[i << 1], self.val[i << 1 | 1])

    def modify(self, i, l, r, u, v, divcnt): # it: [u, v]
        if l > r or l > v or r < u: return
        if self.val[i] <= 2: return
        if l == r:
            self.tot[i] = self.val[i] = divcnt[self.tot[i]]
            return
        m = (l + r) >> 1
        self.modify(i << 1, l, m, u, v, divcnt)
        self.modify(i << 1 | 1, m + 1, r, u, v, divcnt)
        self.tot[i] = self.tot[i << 1] + self.tot[i << 1 | 1]
        self.val[i] = max(self.val[i << 1], self.val[i << 1 | 1])

    def get_sum(self, i, l, r, u, v): # it: [u, v]
        if l > r or l > v or r < u:
            return 0
        if u <= l and r <= v:
            return self.tot[i]
        m = (l + r) >> 1
        lsum = self.get_sum(i << 1, l, m, u, v)
        rsum = self.get_sum(i << 1 | 1, m + 1, r, u, v)
        return lsum + rsum

    def get_max(self, i, l, r, u, v): # it: [u, v]
        if l > r or l > v or r < u:
            return -1
        if u <= l and r <= v:
            return self.val[i]
        m = (l + r) >> 1
        lmax = self.get_max(i << 1, l, m, u, v)
        rmax = self.get_max(i << 1 | 1, m + 1, r, u, v)
        return max(lmax, rmax)


def calc_divcnt():
    divcnt = [1] * 1000100
    for i in range(2, 1000100):
        for j in range(i, 1000100, i):
            divcnt[j] += 1
    return divcnt


def main():
    n, m = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    tree = SegmentTree(n)
    tree.build(a, 1, 1, n)
    divcnt = calc_divcnt()

    for i in range(m):
        t, l, r = [int(x) for x in input().split()]
        if t == 1:
            tree.modify(1, 1, n, l, r, divcnt)
        else:
            print(tree.get_sum(1, 1, n, l, r))


if __name__ == "__main__":
    main()