Euclidean Algorithm and Remainder Count

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

For positive integers a,b, repeatedly replace (a,b) with (b,a mod b) until b=0. Print the gcd and the number of remainder operations.

Input

A single line contains positive integers a and b.

Output

Print gcd and the number of remainder operations separated by one space.

Subtasks

• Subtask 1 (20%): 1≤a,b≤100.
• Subtask 2 (30%): 1≤a,b≤100000.
• Subtask 3 (50%): 1≤a,b≤1000000000.

Examples

Example 1

Input

30 18

Output

6 3

Explanation

Three remainder operations give 12,6,0, hence gcd six.

Example 2

Input

9 9

Output

9 1

Explanation

The one operation 9 mod 9 equals zero.