#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int GCD(int a, int b) { return b ? GCD(b, a % b) : a; };
int main() {
    int m, n;
    while (cin >> m >> n, n || m) {
        int res = 0;
        for (int i = 0; i < n; i++)
            res += pow(m, GCD(n, i));
        if (n & 1) res += n * pow(m, (n + 1) / 2);
        else res += n / 2 * (pow(m, n / 2 + 1) + pow(m, n / 2));
        cout << res / n / 2 << endl;
    }
    return 0;
}