#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;int gcd(int a,int b){	if(b==0) return a;	return gcd(b,a%b);}int Power(int a,int b){	int ans=1;	while(b){		if(b&1) ans=(ans*a);		a=a*a;		b>>=1;	}	return ans;}int main(){	int c,s;	while(scanf("%d%d",&c,&s),c||s){		int ans=0;		for(int i=1;i<=s;i++){			ans=ans+Power(c,gcd(i,s));		}		if(s&1){			ans=ans+s*Power(c,s/2+1);		}		else{			ans=ans+(s/2)*(Power(c,s/2+1)+Power(c,s/2));		}		ans/=(2*s);		printf("%d\n",ans);	}	return 0;}