#include <bits/stdc++.h>
#define fi first
#define se second
#define lo long long
#define inf 1000000000000000000
#define md 1000000007
#define li 100005
#define mp make_pair
#define pb push_back
#define mid (start+end)/2
using namespace std;
int n,q,A[li];
struct SEG{
int bas,son;
lo int res;
int presiz,sufsiz;
vector< pair<int,int> > pre,suf;
}tree[li*4];
SEG merge(SEG A,SEG B){
SEG res1;
res1.bas=A.bas;
res1.son=B.son;
res1.res=A.res+B.res;
int last=-1;
int now=(int)A.suf.size()-1;
int totszB=0;
while(now+1){
pair<int,int> suf_el=A.suf[now];
now--;
while(last+1<(int)B.pre.size() && __gcd(suf_el.fi,B.pre[last+1].fi)>1){
totszB+=B.pre[last+1].se;
last++;
}
res1.res+=1ll*suf_el.se*totszB;
}
if(A.presiz==A.son-A.bas+1){
int last=-1;
while(last+1<(int)B.pre.size() && __gcd(A.pre.back().fi,B.pre[last+1].fi)){
int tut=__gcd(A.pre.back().fi,B.pre[last+1].fi);
last++;
if(tut==A.pre.back().fi){
A.pre.back().se+=B.pre[last].se;
}
else{
A.pre.pb(mp(tut,B.pre[last].se));
}
}
}
if(B.sufsiz==B.son-B.bas+1){
int last=-1;
while(last+1<(int)A.suf.size() && __gcd(A.suf[last+1].fi,B.suf.back().fi)>1){
last++;
int tut=__gcd(A.suf[last].fi,B.suf.back().fi);
if(tut==B.suf.back().fi){
B.suf.back().se+=A.suf[last].se;
}
else{
B.suf.pb(mp(tut,A.suf[last].se));
}
}
}
res1.pre=A.pre;
res1.suf=B.suf;
res1.presiz=res1.sufsiz=0;
for(int i=0;i<(int)A.pre.size();i++) res1.presiz+=A.pre[i].se;
for(int i=0;i<(int)B.suf.size();i++) res1.sufsiz+=B.suf[i].se;
return res1;
}
void build(int node,int start,int end){
if(start==end){
tree[node].bas=start;
tree[node].son=end;
if(A[start]>1){
tree[node].pre.pb(mp(A[start],1));
tree[node].suf.pb(mp(A[start],1));
tree[node].presiz=tree[node].sufsiz=tree[node].res=1;
}
return ;
}
build(node*2,start,mid),build(node*2+1,mid+1,end);
tree[node]=merge(tree[node*2],tree[node*2+1]);
}
SEG query(int node,int start,int end,int l,int r){
if(start>=l && end<=r) return tree[node];
if(mid>=l){
if(mid+1<=r)
return merge(query(node*2,start,mid,l,r),query(node*2+1,mid+1,end,l,r));
else
return query(node*2,start,mid,l,r);
}
else{
return query(node*2+1,mid+1,end,l,r);
}
}
void update(int node,int start,int end,int l,int r,int val){
if(start>end || start>r || end<l) return ;
if(start>=l && end<=r){
tree[node].pre.clear();
tree[node].suf.clear();
tree[node].res=tree[node].presiz=tree[node].sufsiz=0;
if(val>1){
tree[node].pre.pb(mp(val,1));
tree[node].suf.pb(mp(val,1));
tree[node].presiz=tree[node].sufsiz=tree[node].res=1;
}
return ;
}
update(node*2,start,mid,l,r,val),update(node*2+1,mid+1,end,l,r,val);
tree[node]=merge(tree[node*2],tree[node*2+1]);
}
int main(){
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",&A[i]);
build(1,1,n);
while(q--){
int ty,num1,num2;
scanf("%d %d %d",&ty,&num1,&num2);
if(ty==1){
update(1,1,n,num1,num1,num2);
}
else{
lo int yaz=query(1,1,n,num1,num2).res;
printf("%lld\n",yaz);
}
}
return 0;
}
