#include <bits/stdc++.h>
#define sz(c) int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
using namespace std;
using i64 = long long;
using vii = vector<pair<int,int>>;
struct node {
i64 count=-1;
vii p,s;
void set(int x) {
count=(x==1 ? 0 : 1);
p=s={make_pair(x,1)};
}
};
i64 merge_count(const vii &S, const vii &P) {
i64 res=0,r=0,psum=0;
per(l,0,sz(S)) {
while (r<sz(P) && __gcd(S[l].first,P[r].first)>1) {
psum+=P[r].second;
r+=1;
}
res+=S[l].second*psum;
}
return res;
}
// s3 s2 s1 s0 p0 p1 p2 p3
node merge_nodes(const node &L, const node &R) {
if (L.count==-1) return R;
if (R.count==-1) return L;
node res;
res.count=L.count+R.count+merge_count(L.s,R.p);
res.p=L.p;
auto &p=res.p;
int cur=p.back().first;
for (const auto &x:R.p) {
cur=__gcd(cur,x.first);
if (cur==p.back().first) {
p.back().second+=x.second;
} else {
p.emplace_back(cur,x.second);
}
}
// a.s3 a.s2 a.s1 a.s0 b.s3 b.s2 b.s1 b.s0
// c.s7 c.s6 c.s5 c.s4 c.s3 c.s2 c.s1 c.s0
res.s=R.s;
auto &s=res.s;
cur=s.back().first;
for (const auto &x:L.s) {
cur=__gcd(cur,x.first);
if (cur==s.back().first) {
s.back().second+=x.second;
} else {
s.emplace_back(cur,x.second);
}
}
return res;
}
// int const N=1<<17;
int const N=8;
int n,q;
node tr[2*N];
void update(int i, int x) {
tr[i+=N].set(x);
for (i/=2; i>0; i/=2) { tr[i]=merge_nodes(tr[2*i],tr[2*i+1]); }
}
i64 get(int l, int r) {
// cerr<<l<<" "<<r<<endl;
node L,R;
L.count=R.count=-1;
l+=N;
r+=N;
while (l<=r) {
if (l%2==1) {
L=merge_nodes(L,tr[l]);
// cerr<<"merge: L and ("<<l<<","<<tr[l].count<<")"<<endl;
}
if (r%2==0) {
R=merge_nodes(tr[r],R);
// cerr<<"merge: ("<<r<<","<<tr[r].count<<") and R"<<endl;
}
l=(l+1)/2;
r=(r-1)/2;
}
// cerr<<L.count<<endl;
// cerr<<R.count<<endl;
return merge_nodes(L,R).count;
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
cout<<fixed<<setprecision(10);
cin>>n>>q;
rep(i,0,n) {
int x;
cin>>x;
tr[i+N].set(x);
// cerr<<x<<" ";
}
// cerr<<endl;
per(i,1,N) { tr[i]=merge_nodes(tr[2*i],tr[2*i+1]); }
// cerr<<tr[1].count<<endl;
rep(iq,0,q) {
int t,l,r;
cin>>t>>l>>r;
if (t==1) { update(l-1,r); } else { cout<<get(l-1,r-1)<<'\n'; }
}
return 0;
}
