#include <iostream>
using namespace std;

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int tmp = x;
    x = y;
    y = tmp - (a / b) * y;
    return d;
}

int main() {
    int a, b;
    cin >> a >> b;
    int x, y;
    int d = exgcd(a, b, x, y);
    x = ((x % b) + b) % b;
    cout << x << '\n';
    return 0;
}

/**
        Author:    BoopsA
        Created:   2020-11-30 17:50:46
        Modified:  2020-11-30 18:46:54
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll mod;

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

ll mul(ll a, ll b) {
    ll res = 0;
    while (b) {
        if (b & 1) res = (res + a) % mod;
        a = (a + a) % mod;
        // cout << a << ' ';
        b >>= 1;
    }
    return res;
}

ll fpow(ll a, ll b) {
    ll res = 1 % mod;
    while (b) {
        if (b & 1) res = mul(res, a);
        a = mul(a, a);
        // cout << a << ' ';
        b >>= 1;
    }
    return res;
}

ll phi(ll n) {
    ll res = n;
    for (ll i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            n /= i;
            res = res / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

int main() {
#ifdef LOCAL_DEFINE
    freopen("D:/ACM/in.txt", "r", stdin);
#endif

    ll l;
    int e = 0;
    while (cin >> l) {
        if (l == 0) break;
        printf("Case %d: ", ++e);
        l /= gcd(8, l);
        l = 9 * l;
        ll tmp = phi(l);
        mod = l;
        ll res = 2e9;
        for (ll i = 1; i <= tmp / i; i++) {
            if (tmp % i == 0) {
                if (fpow(10, i) == 1) res = min(res, i);
                if (i != tmp / i) {
                    if (fpow(10, tmp / i) == 1) res = min(res, tmp / i);
                }
            }
        }
        if (res != 2e9) cout << res << '\n';
        else cout << 0 << '\n';
    }


#ifdef LOCAL_DEFINE
    printf("Time elapsed: %.3fs\n", 1.0 * clock() / CLOCKS_PER_SEC);
#endif

    return 0;
}

/**
        Author:    BoopsA
        Created:   2020-11-26 20:25:20
        Modified:  2020-11-26 21:12:11
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;

int phi[N];
int primes[N], v[N];
int cnt;

void init() {
    cnt = 0;
    phi[1] = 1;
    for (int i = 2; i < N; i++) {
        if (v[i] == 0) {
            v[i] = i;
            primes[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt; j++) {
            if (primes[j] > v[i] || i * primes[j] >= N) break;
            v[i * primes[j]] = primes[j];
            if (i % primes[j] == 0) {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
            phi[i * primes[j]] = phi[i] * phi[primes[j]];
        }
    }
    for (int i = 1; i < N; i++) phi[i] += phi[i - 1];
}

int main() {
//  freopen("D:/ACM/in.txt", "r", stdin);
    // freopen("D:/ACM/out1.txt", "w", stdout);
    int t;
    cin >> t;
    init();
    for (int e = 1; e <= t; e++) {
        int n;
        cin >> n;
        printf("%d %d %d\n", e, n, 2 * (phi[n] - phi[1]) + 3);
    }
    return 0;
}

/**
        Author:    BoopsA
        Created:   2020-11-26 17:55:16
        Modified:  2020-11-26 19:44:31
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;


int primes[N], v[N];
int cnt;
int a0, a1, b0, b1;

void init() {
    cnt = 0;
    for (int i = 2; i < N; i++) {
        if (!v[i]) {
            primes[++cnt] = i;
            v[i] = i;
        }
        for (int j = 1; j <= cnt; j++) {
            if (primes[j] > v[i] || i >= N / primes[j]) break;
            v[i * primes[j]] = primes[j];
        }
    }
}

int gcd(int a, ll b) {
    return b ? gcd(b, a % b) : a;
}

int fpow(int a, int n) {
    int res = 1;
    while (n) {
        if (n & 1) res = res * a;
        a *= a;
        n >>= 1;
    }
    return res;
}

int x;
int res;
int len;
int f[N], nums[N];
void dfs(int a) {
    if (a > len) {
        if (gcd(x, a0) == a1 && b0 / gcd(b0, x) * x == b1) res++;
        return;
    }
    for (int i = 0; i <= nums[a]; i++) {
        x *= fpow(f[a], i);
        dfs(a + 1);
        x /= fpow(f[a], i);
    }
}

int main() {
//  freopen("D:/ACM/in.txt", "r", stdin);
    int n;
    cin >> n;
    init();
    while (n--) {
        cin >> a0 >> a1 >> b0 >> b1;
        int tmp = b1;
        len = 0;
        for (int i = 1; i <= cnt && primes[i] <= tmp / primes[i]; i++) {
            if (tmp % primes[i] == 0) {
                f[++len] = primes[i];
                int c = 0;
                while (tmp % primes[i] == 0) {
                    c++;
                    tmp /= primes[i];
                }
                nums[len] = c;
            }
        }
        if (tmp > 1) {
            f[++len] = tmp;
            nums[len] = 1;
        }
        x = 1;
        res = 0;
        dfs(1);
        cout << res << '\n';
    }
    return 0;
}

/**
        Author:    BoopsA
        Created:   2020-11-14 18:47:07
        Modified:  2020-11-14 18:59:03
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

ll n, k;

int main() {
    //freopen("D:/ACM/in.txt", "r", stdin);
    cin >> n >> k;
    ll res = n * k;
    for (ll l = 1, r; l <= k && l <= n; l = r + 1) {
        r = min(k / (k / l), n);
        res = res - (k / l) * (l + r) * (r - l + 1) / 2;
    }
    cout << res << '\n';
    return 0;
}

/**
        Author:    BoopsA
        Created:   2020-11-14 17:00:53
        Modified:  2020-11-14 18:41:10
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int p[11] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int c[11];
ll res = 2e9;
int n;
ll num = 1, sum = 0;

int fpow(int a, int n) {
    int res = 1;
    while (n) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}

void dfs(int a) {
    if (a == 11) {
        int cnt = 0;
        // if (c[1] == 5) {
        //  for (int i = 1; i <= 10; i++) cout << c[i] << ' ';
        //  cout << num << '\n';
        // }
        for (int i = 1; 1ll * i * i <= num; i++) {
            if (num % i == 0) {
                cnt++;
                if (i != num / i) cnt++;
            }
        }
        if (sum == cnt) {
            res = min(res, num);
        }
        if (sum < cnt) {
            res = num;
            sum = cnt;
        }
        return;
    }
    for (int i = 0; i <= c[a - 1]; i++) {
        c[a] += i;
        num *= fpow(p[a], i);
        if (num > n) {
            num /= fpow(p[a], i);
            c[a] -= i;
            break;
        }
        dfs(a + 1);
        num /= fpow(p[a], i);
        c[a] -= i;
    }
}

int main() {
//  freopen("D:/ACM/in.txt", "r", stdin);
    cin >> n;
    c[0] = 30;
    dfs(1);
    cout << res << '\n';
    return 0;
}

/**
        Author:    BoopsA
        Created:   2020-10-22 12:47:13
        Modified:  2020-10-22 13:09:58
**/
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;

ll fpow(ll a, int n) {
    ll res = 1;
    while (n) {
        if (n & 1) res *= a;
        a *= a;
        n >>= 1;
    }
    return res;
}

int cnt;
int primes[N], v[N];
int nums[N];
void init(int x) {
    cnt = 0;
    for (int i = 2; i <= x; i++) {
        if (!v[i]) {
            v[i] = i;
            primes[++cnt] = i;
        }
        for (int j = 1; j <= cnt; j++) {
            if (primes[j] > v[i] || 1ll * i * primes[j] > x) break;
            v[i * primes[j]] = primes[j];
        }
    }
}

int main() {
//  freopen("C:/ACM/in.txt", "r", stdin);
    int n;
    cin >> n;
    init(n);

    int res = 0;
    for (int i = 1; i <= cnt; i++) {
        ll p = primes[i];
        for (int j = 1; fpow(p, j) <= n; j++) {
            nums[i] += n / fpow(p, j);
        }
    }
    for (int i = 1; i <= cnt; i++) {
        if (nums[i] == 0) break;
        cout << primes[i] << ' '<< nums[i] << '\n';
    }
    return 0;
}

/**
        Author:    BoopsA
        Created:   2020-10-22 09:49:38
        Modified:  2020-10-22 12:23:16
**/
#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 5e4 + 10;

int primes[N], v[N];
int cnt;
bool f[(int)1e6 + 10];
void init() {
    cnt = 0;
    for (int i = 2; i < N; i++) {
        if (!v[i]) {
            v[i] = i;
            primes[++cnt] = i;
        }
        for (int j = 1; j <= cnt; j++) {
            if (primes[j] > v[i] || 1ll * i * primes[j] >= N) break;
            v[i * primes[j]] = primes[j];
        }
    }
}

int main() {
//  freopen("C:/ACM/in.txt", "r", stdin);
    init();
    int l, r;
    while (cin >> l >> r) {
        memset(f, 0, sizeof f);
        for (int j = 1; j <= cnt; j++) {
            int p = primes[j];
            if (1ll * p * p > r) break;
            int ll = max(2, (int)ceil((double)l / p));
            int rr = r / p;
            for (int k = ll; k <= rr; k++) {
                f[p * k - l] = 1;
            }
        }

        if (l == 1) f[0] = 1;
        std::vector<int> v;
        for (ll i = l; i <= r; i++) {
            if (!f[i - l]) v.push_back(i);
        }
        if ((int)v.size() <= 1) {
            cout << "There are no adjacent primes.\n";
            continue;
        }
        int max_r = 0;
        int min_r = (int)1e6;
        int res1, res2, res3, res4;
        for (int i = 1; i < (int)v.size(); i++) {
            if (max_r < v[i] - v[i - 1]) {
                res1 = v[i - 1];
                res2 = v[i];
                max_r = v[i] - v[i - 1];
            }
            if (min_r > v[i] - v[i - 1]) {
                res3 = v[i - 1];
                res4 = v[i];
                min_r = v[i] - v[i - 1];
            } 
        }
        printf("%d,%d are closest, %d,%d are most distant.\n", res3, res4, res1, res2);
    }
    return 0;
}

/**
      Author:    BoopsA
      Created:   2020-09-04 09:29:00
      Modified : 2020-09-04 10:40:46
**/
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 500010;

int n, m;
ll a[N], b[N], c[N];
struct Node {
    int l, r;
    ll val;
} t[N * 4];

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) {
        t[p].val = b[l];
        return;
    }
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    t[p].val = gcd(t[p * 2].val, t[p * 2 + 1].val);
}

void change(int p, int x, ll d) {
    if (t[p].l == t[p].r) {
        t[p].val += d;
        return;
    }
    int mid = (t[p].l + t[p].r) / 2;
    if (x <= mid) change(p * 2, x, d);
    else change(p * 2 + 1, x, d);
    t[p].val = gcd(t[p * 2].val, t[p * 2 + 1].val);
}

ll ask(int p, int l, int r) {
    if (t[p].l >= l && r >= t[p].r) return abs(t[p].val);
    int mid = (t[p].l + t[p].r) / 2;
    ll val = 0;
    if (l <= mid) val = gcd(ask(p * 2, l, r), val);
    if (r > mid) val = gcd(ask(p * 2 + 1, l , r), val);

    return abs(val);
}

void add(int x, ll y) {
    for (; x <= n; x += x & (-x)) c[x] += y;
}

ll ask2(int x) {
    ll res = 0;
    for (; x; x -= x & (-x)) res += c[x];
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++) b[i] = a[i] - a[i - 1];

    build(1, 1, n);
    while (m--) {
        char c;
        cin >> c;
        if (c == 'Q') {
            int l, r;
            scanf("%d%d", &l ,&r);
            ll tar = ask2(l) + a[l];
            cout << gcd(ask(1, l + 1, r), tar) << '\n';
        } else {
            int l ,r;
            ll d;
            scanf("%d%d%lld", &l, &r, &d);
            change(1, l, d);
            if (r < n) change(1, r + 1, -d);  //这个判断很关键，change函数的前提是x要存在
            add(l, d);
            add(r + 1, -d);
        }
    }

    return 0;
}

/**
        Author:    BoopsA
        Created:   2020-09-10 17:28:22
        Modified:  2020-09-11 17:45:28
**/
//我们是冠军!!
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;

int n, t[N];
pair<int, int> res[N];
struct Node1 {
    int val;
    int idx;
} a[N];
struct Node2 {
    int pre, ne;
} b[N];

bool cmp(Node1 a, Node1 b) {
    return a.val < b.val;
}

int main() {
//  freopen("C:/ACM/in.txt", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].val;
        t[i] = a[i].val;
        a[i].idx = i;
    }
    sort(a + 1, a + 1 + n, cmp);


    b[a[1].idx].pre = 0; //为0代表删除
    b[a[1].idx].ne = a[2].idx;
    b[a[n].idx].pre = a[n - 1].idx;
    b[a[n].idx].ne = 0;

    for (int i = 2; i < n; i++) {
        b[a[i].idx].pre = a[i - 1].idx;
        b[a[i].idx].ne = a[i + 1].idx;
    }

    for (int i = n; i >= 2; i--) {
        if (b[i].pre && b[i].ne) {
            if (abs(t[b[i].pre] - t[i]) < abs(t[b[i].ne] - t[i])) {
                res[i] = make_pair((int)abs(t[b[i].pre] - t[i]), b[i].pre);
            } else if (abs(t[b[i].pre] - t[i]) > abs(t[b[i].ne] - t[i])) {
                res[i] = make_pair((int)abs(t[b[i].ne] - t[i]), b[i].ne);
            } else {
                if (t[b[i].pre] < t[b[i].ne])
                    res[i] = make_pair((int)abs(t[b[i].pre] - t[i]), b[i].pre);
                else 
                    res[i] = make_pair((int)abs(t[b[i].ne] - t[i]), b[i].ne);
            }
        } else if (b[i].pre) {
            res[i] = make_pair((int)abs(t[b[i].pre] - t[i]), b[i].pre);
        } else {
            res[i] = make_pair((int)abs(t[b[i].ne] - t[i]), b[i].ne);
        }

        b[b[i].pre].ne = b[i].ne;
        b[b[i].ne].pre = b[i].pre;
    }
    for (int i = 2; i <= n; i++) cout << res[i].first << ' ' << res[i].second << '\n';

    return 0;
}