#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 100005;
int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}
struct Message {
	vector < pair < int, int > > pre, suf;
	long long ans;
};
Message one_number(int x) {
	Message res;
	res.pre.push_back(make_pair(x, 1));
	res.suf.push_back(make_pair(x, 1));
	if (x > 1) {
		res.ans = 1;
	} else {
		res.ans = 0;
	}
	return res;
}
vector < pair < int, int > > merge_gcd(vector < pair < int, int > > x, vector < pair < int, int > > y, int type) {
	if (x.empty()) {
		return y;
	}
	if (y.empty()) {
		return x;
	}
	if (type == 1) {
		reverse(x.begin(), x.end());
		reverse(y.begin(), y.end());
	}
	vector < pair < int, int > > res = x;
	pair < int, int > & last = res.back();
	for (pair < int, int > i : y) {
		int g = gcd(last.first, i.first);
		if (last.first == g) {
			last.second += i.second;
		} else {
			res.push_back(make_pair(g, i.second));
			last = res.back();
		}
	}
	if (type == 1) {
		reverse(res.begin(), res.end());
	}
	return res;
}
Message operator + (const Message & a, const Message & b) {
	Message res;
	res.ans = a.ans + b.ans;
	res.pre = merge_gcd(a.pre, b.pre, 0);
	res.suf = merge_gcd(b.suf, a.suf, 1);
	if (a.suf.size() > 0 && b.pre.size() > 0) {
		for (int i = 0, j = 0, sum = 0; i < (int)a.suf.size(); i++) {
			while (j < (int)b.pre.size() && gcd(a.suf[i].first, b.pre[j].first) > 1) {
				sum += b.pre[j].second;
				j++;
			}
			if (j != 0) {
				res.ans += a.suf[i].second * sum;
			}
		}
	}
	return res;
}
int a[N];
struct Node {
	int l, r;
	Message m;
} node[4 * N];
void push_up(int p) {
	node[p].m = node[2 * p].m + node[2 * p + 1].m;
}
void build(int p, int l, int r) {
	node[p].l = l;
	node[p].r = r;
	if (l == r) {
		node[p].m = one_number(a[l]);
	} else {
		int mid = (l + r) / 2;
		build(2 * p, l, mid);
		build(2 * p + 1, mid + 1, r);
		push_up(p);
	}
}
void modify(int p, int x, int v) {
	if (node[p].l == node[p].r) {
		node[p].m = one_number(v);
	} else {
		int mid = (node[p].l + node[p].r) / 2;
		if (x <= mid) {
			modify(2 * p, x, v);
		} else {
			modify(2 * p + 1, x, v);
		}
		push_up(p);
	}
}
Message query(int p, int l, int r) {
	if (l <= node[p].l && node[p].r <= r) {
		return node[p].m;
	} else {
		int mid = (node[p].l + node[p].r) / 2;
		if (r <= mid) {
			return query(2 * p, l, r);
		} else if (mid + 1 <= l) {
			return query(2 * p + 1, l, r);
		} else {
			return query(2 * p, l, r) + query(2 * p + 1, l, r);
		}
	}
}
int main() {
	int n, q;
	scanf("%d %d", &n, &q);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	build(1, 1, n);
	for (int op, x, v, l, r, i = 1; i <= q; i++) {
		scanf("%d", &op);
		if (op == 1) {
			scanf("%d %d", &x, &v);
			modify(1, x, v);
		} else {
			scanf("%d %d", &l, &r);
			printf("%lld\n", query(1, l, r).ans);
		}
	}
	return 0;
}