/*
_/_/_/_/    _/_/_/_/_/  _/_/_/
_/      _/      _/    _/      _/
_/      _/      _/    _/      _/
_/      _/      _/    _/      _/
_/      _/      _/    _/  _/  _/
_/      _/  _/  _/    _/    _/_/
_/_/_/_/      _/_/     _/_/_/_/_/

_/_/_/_/    _/    _/  _/      _/
_/      _/   _/  _/   _/_/  _/_/
_/      _/    _/_/    _/ _/_/ _/
_/      _/     _/     _/  _/  _/
_/      _/    _/_/    _/      _/
_/      _/   _/  _/   _/      _/
_/_/_/_/    _/    _/  _/      _/

_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/         _/     _/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/     _/_/_/_/_/ _/_/_/_/_/

_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/         _/     _/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/     _/_/_/_/_/ _/_/_/_/_/
*/
#include <cassert>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <iomanip>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef unsigned long long ull;

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

void exGcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1;
    y = 0;
    return;
  }
  exGcd(b, a % b, y, x);
  y -= a / b * x;
}

int inv(int a, int mod) {
  int x, y;
  exGcd(a, mod, x, y);
  return (x + mod) % mod;
}

const int N = 100010;

int a[N], b[N], ans[N];

int main() {
#ifdef ELEGIA
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;
  map<int, vector<int>> qry;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> b[i];
    if (a[i] && b[i]) {
      int g = gcd(m, gcd(a[i], b[i]));
      a[i] /= g;
      b[i] /= g;
      qry[m / g].push_back(i);
    } else if (a[i] == 0) ans[i] = 0;
    else if (b[i] == 0) ans[i] = 1;
  }
  for (auto [md, qs] : qry) {
    vector<int> per = {0, 1};
    int mod = md;
    per.reserve(6 * mod);
    while (true) {
      int f = (per.back() + per[per.size() - 2]) % mod;
      if (f == 0) break;
      per.push_back(f);
    }
    map<pair<int, int>, int> mp;
    auto significant = [&](int& x, int& y) {
      int xx, yy;
      exGcd(x, mod, xx, yy);
      if (xx < 0) xx += mod;
      int g = mod / gcd(x, mod);
      x = x * (ull)xx % mod;
      y = y * (ull)xx % g;
    };
    for (int i = 2; i != per.size(); ++i) {
      int x = per[i - 1], y = per[i];
      significant(x, y);
      mp[make_pair(x, y)] = per.size() - i + 1;
    }
    for (int i : qs) {
      significant(a[i], b[i]);
      auto it = mp.find(make_pair(a[i], b[i]));
      if (it == mp.end()) ans[i] = -1;
      else ans[i] = it->second;
    }
  }
  for (int i = 1; i <= n; ++i) cout << ans[i] << '\n';

#ifdef ELEGIA
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}