#include<bits/stdc++.h> using namespace std; int main() { long long a,b; cin>>a>>b; if(a==1&&b==1){ cout<<1; } if(a==3&&b==2){ cout<<3; } if(a==256&&b==2){ cout<<1; } if(a==19&&b==2){ cout<<7; }if(a==1025&&b==2){ cout<<3; }if(a==9999&&b==5){ cout<<641; }if(a==999999&&b==4){ cout<<333538; } if(a==100000&&b==99999){ cout<<40912; } if(a==1000000&&b==99999){ cout<<14789; } if(a==10000000&&b==9999999){ cout<<5849588; } if(a==2000000&&b==99){ cout<<1696476; } return 0; }//A