#include <bits/stdc++.h>

using namespace std;

// #define int long long
#define x first
#define y second
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

inline void debug() { cerr << '\n'; }
template<typename Type, typename... Other>
inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }
#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a);

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1000010;
const int INF = 0x3f3f3f3f;

template<typename Type>
inline void read(Type &res)
{
    res = 0;
    int ch = getchar(), flag = 0;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    res = flag ? -res : res;
}
template<typename Type, typename... Other>
inline void read(Type &res, Other&... y) { read(res), read(y...); }

int k, m, ans;
deque<PII> dq;
bool vis[N];

signed main()
{
	// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> k >> m;

    dq.push_front({1, 1});
    vis[1] = true;
    
    while (!dq.empty())
    {
        // auto [cur, val] = dq.front(); dq.pop_front();
        PII x = dq.front(); dq.pop_front();
        int cur = x.x, val = x.y;
        // int cur = dq.front().x, val = dq.front().y; dq.pop_front();
        if (!cur) return cout << val << '\n', 0;
        if (!vis[cur * m % k])
        {
            dq.push_front({cur * m % k, val});
            vis[cur * m % k] = true;
        }
        if (!vis[(cur + 1) % k])
            dq.push_back({(cur + 1) % k, val + 1});
    }

	return 0;
}