// 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 dp[N][55];
 
void dfs(int now, int sum)
{
	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);
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i < m; i ++) dfs(i, i);
	for(int i = 1; i <= 55; i ++) if(dp[0][i]) {cout << i << '\n'; return 0;}
	return 0;
}