피자 자르기

오늘 밤 여러분은 정기적으로 열리는 GAUSS 천체 관측 행사 중 하나에 참석하며, 늘 그렇듯 무료 피자가 제공된다. $N$명의 참가자는 하나의 거대한 $A\times B$ 직사각형 피자를 주문했으며, 여러분은 이를 서로 나누어 먹어야 한다. 저녁 내내 크기가 제각각인 구형 물체를 바라보는 단조로움을 피하고자, 여러분 모두는 크기가 동일한 정사각형 피자 조각만 먹기로 했다. 모든 참가자가 배고프므로 각자 적어도 한 조각씩 먹어야 한다. 또한 피자가 남는 것은 몹시 아까운 일이므로, 피자 전체를 동일한 정사각형 조각들로 만들어야 한다. 여러분은 무척 아끼는 피자 절단기를 가져왔으며, 그것이 너무 소중하기 때문에 가능한 한 적은 횟수의 직선 절단만 하고 싶다. 아주 큰 피자를 올려놓은 아주 큰 탁자 위에서 피자 조각들을 옮길 수 있으므로, 여러 조각을 한 번의 절단으로 자를 수 있다.

입력은 공백으로 구분된 $N$ ($2 \le N \le 10^{18}$), $A$와 $B$ ($1 \le A, B \le 10^{18}$)가 있는 한 줄로 주어진다.

피자를 크기가 동일한 정사각형 조각 적어도 $N$개로 나누는 데 필요한 최소 절단 횟수를 하나의 수로 출력한다.