// Problem: B. Small Multiple
// Contest: undefined - NOIP2024训练赛 08
// URL: http://www.noi.ac/contest/1160/problem/2678
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define fi first
#define se second
#define PII pair<int, int>

using namespace std;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;

int n, m;
bool vis[N], dp[N][55];
 
list<PII> q;
 
// void dfs(int now, int sum)
// {
	// if()
	// if(sum >= 55 || dp[now][sum]) return;
	// dp[now][sum] = true;
	// for(int i = 0; i < m; i ++) dfs((now * m + i) % n, sum + i);
// }

void bfs() 
{
	q.push_front({1, 1});
	vis[1] = true;
	while(!q.empty()) 
	{
		int num = q.front().fi, val = q.front().se; q.pop_front();
		if(!num) 
		{
			cout << val << '\n';
			return;
		}
		if(!vis[m * num % n]) 
		{
			q.push_front({m * num % n, val});
			vis[m * num % n] = true;
		}
		if(!vis[(num + 1) % n]) 
			q.push_back({(num + 1) % n, val + 1});
	}
	return;
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m; 
	bfs();
	return 0;

}