Giảm theo Euclid chia dư (Euclidean Algorithm and Remainder Count)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho hai số nguyên dương $a,b$. Lặp phép biến đổi $(a,b)\leftarrow(b,a\bmod b)$ cho tới khi $b=0$. In UCLN ban đầu và số lần đã thực hiện phép lấy dư.

Input

Một dòng chứa hai số nguyên dương $a,b$.

Output

In UCLN và số bước, cách nhau một dấu cách.

Subtask

• Subtask 1 (20%): $1\le a,b\le100$.
• Subtask 2 (30%): $1\le a,b\le10^5$.
• Subtask 3 (50%): $1\le a,b\le10^9$.

Ví dụ

Ví dụ 1

Input

30 18

Output

6 3

Giải thích

30%18=12 (bước1), 18%12=6 (bước2), 12%6=0 (bước3); UCLN6 và 3 bước.

Ví dụ 2

Input

9 9

Output

9 1

Giải thích

9%9=0 phải tính là một lần lấy dư, nên in 9 1.