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
from utils.oj import J


def f0(ns, qs, ds):
    ns = ns[:]
    ans = []
    for op, ll, rr in qs:
        if op == 2:
            ans.append(sum(ns[ll - 1: rr]))
        else:
            for i in range(ll - 1, rr):
                ns[i] = ds[ns[i]]
    return ans


class SegTreeDyn:
    class Node:
        def __init__(self):
            self.sum = 0
            self.reach = 0

    def __init__(self, arr, ds):
        self.n = len(arr) - 1
        self.nodes = [self.Node() for _ in range(len(arr) << 2)]
        self.ds = ds
        self.build_helper(1, 0, self.n, arr)

    def build_helper(self, xi, xl, xr, arr):
        ii = self.nodes[xi]
        if xl == xr:
            ii.sum = arr[xl]
            ii.reach = int(ii.sum <= 2)
            return
        xm = (xl + xr) >> 1
        self.build_helper(xi << 1, xl, xm, arr)
        self.build_helper((xi << 1) | 1, xm + 1, xr, arr)
        self.pull_up(xi)

    def pull_up(self, xi):
        ii = self.nodes[xi]
        ll = self.nodes[xi << 1]
        rr = self.nodes[(xi << 1) | 1]
        ii.sum = ll.sum + rr.sum
        ii.reach = ll.reach & rr.reach

    def dec(self, ll, rr):
        self.dec_helper(1, 0, self.n, ll, rr)

    def dec_helper(self, xi, xl, xr, ql, qr):
        ii = self.nodes[xi]
        if xl == xr:
            ii.sum = self.ds[ii.sum]
            ii.reach = int(ii.sum <= 2)
            return
        if ql <= xl and xr <= qr and ii.reach:
            return
        xm = (xl + xr) >> 1
        if ql <= xm and qr >= xl:
            self.dec_helper(xi << 1, xl, xm, ql, qr)
        if ql <= xr and qr > xm:
            self.dec_helper((xi << 1) | 1, xm + 1, xr, ql, qr)
        self.pull_up(xi)

    def query_sum(self, ll, rr):
        return self.query_sum_helper(1, 0, self.n, ll, rr)

    def query_sum_helper(self, xi, xl, xr, ql, qr):
        if ql <= xl and xr <= qr:
            return self.nodes[xi].sum
        xm = (xl + xr) >> 1
        ans = 0
        if ql <= xm and qr >= xl:
            ans += self.query_sum_helper(xi << 1, xl, xm, ql, qr)
        if ql <= xr and qr > xm:
            ans += self.query_sum_helper((xi << 1) | 1, xm + 1, xr, ql, qr)
        self.pull_up(xi)
        return ans


def f1(ns, qs, ds):
    seg = SegTreeDyn(ns, ds)
    ans = []
    for op, ll, rr in qs:
        ll -= 1
        rr -= 1
        if op == 2:
            ans.append(seg.query_sum(ll, rr))
        else:
            seg.dec(ll, rr)
    return ans


def get_ds(n):
    ans = [2] * (n + 1)
    ans[1] = 1
    for i in range(2, n // 2 + 2):
        for j in range(i + i, n + 1, i):
            ans[j] += 1
    # print(ans)
    return ans


def test():
    import numpy as np
    for t in range(10000):
        print(t)
        n = np.random.randint(1, 100)
        q = np.random.randint(5, 100)
        ns = np.random.randint(1, 100, n).tolist()
        ds = get_ds(max(ns))
        qs = []
        for _ in range(q):
            op = np.random.randint(1, 2 + 1)
            li, ri = sorted(np.random.randint(1, n + 1, 2))
            qs.append((op, li, ri))
        J.same([f0, f1], **{"ns": ns, "qs": qs, "ds": ds})


if __name__ == '__main__':
    # test()
    # J.multi(test)
    # exit()

    n, q = map(int, input().split())
    ns = list(map(int, input().split()))
    qs = [list(map(int, input().split())) for _ in range(q)]
    ds = get_ds(max(ns))
    ans = f0(ns, qs, ds)
    for x in ans:
        print(x)
