// Problem   Let it Bead
// Algorithm Algebra, Burnside-Cauchy-Frobenius Lemma
// Runtime   O(s * log(s))
// Author    Walter Guttmann
// Date      24.11.1999

#include <cassert>
#include <fstream>
#include <iostream>
#define in cin

using namespace std;

int gcd (int a, int b)
{
  return b ? gcd(b,a%b) : a;
}

main ()
{
  int c, s;
  while (in >> c >> s)
  {
    if (c == 0 || s == 0) break;
    assert (1 <= c && 1 <= s && c * s <= 32);

    // powers of c
    int p[64];
    p[0] = 1;
    for (int k=0 ; k<s ; k++)
      p[k+1] = p[k] * c;

    // reflection part
    int count = s&1 ? s * p[s/2 + 1] : (s/2) * (p[s/2] + p[s/2 + 1]);
    // rotation part
    for (int k=1 ; k<=s ; k++)
      count += p[gcd(k,s)];
    assert (count % (2 * s) == 0);
    count /= 2 * s;

    cout << count << endl;
  }
  return 0;
}

