#include <iostream>
#include <vector>
#include <print>

using namespace std;

const int MOD = 100003;
const int MAX = 3000005;

// 各数の約数の和を前計算する
vector<int> sigma(MAX, 0);
void precompute() {
    for (int i = 1; i < MAX; ++i) {
        for (int j = i; j < MAX; j += i) {
            sigma[j] = (sigma[j] + i) % MOD;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    precompute();

    long long n, k;
    if (!(cin >> n >> k)) return 0;

    // 訪れた位置のステップ数を記録（周期検出用）
    // 2回目以降は必ず MOD(100003) 未満になる
    vector<long long> visited(MOD, -1);
    vector<long long> history;

    long long curr = n;
    long long step = 1;

    while (step <= k) {
        // 現在の値が MOD 未満のときに周期チェックを行う
        if (curr < MOD) {
            if (visited[curr] != -1) {
                // 周期を発見
                long long cycle_start = visited[curr];
                long long cycle_len = step - cycle_start;
                long long rem_steps = (k - step + 1) % cycle_len;
                
                // 周期内の該当する位置の値を返して終了
                long long ans_idx = cycle_start - 1 + rem_steps;
                std::println("{}", history[ans_idx]);
                return 0;
            }
            visited[curr] = step;
        }

        history.push_back(curr);

        // 次の項へ（Kに達したらループを抜ける）
        if (step == k) break;
        curr = sigma[curr];
        step++;
    }

    std::println("{}", curr);

    return 0;
}