description: Consider a sequence of distinct integers a_1, …, a_n, each representing one node of a graph. There is an edge between two nodes if the two values are not coprime, i. e. they have a common divisor greater than 1.
  
  There are q queries, in each query, you want to get from one given node a_s to another a_t. In order to achieve that, you can choose an existing value a_i and create new value a_{n+1} = a_i ⋅ (1 + a_i), with edges to all values that are not coprime with a_{n+1}. Also, n gets increased by 1. You can repeat that operation multiple times, possibly making the sequence much longer and getting huge or repeated values. What's the minimum possible number of newly created nodes so that a_t is reachable from a_s?
  
  Queries are independent. In each query, you start with the initial sequence a given in the input.
  
  Input
  
  The first line contains two integers n and q (2 ≤ n ≤ 150 000, 1 ≤ q ≤ 300 000) — the size of the sequence and the number of queries.
  
  The second line contains n distinct integers a_1, a_2, …, a_n (2 ≤ a_i ≤ 10^6, a_i ≠ a_j if i ≠ j).
  
  The j-th of the following q lines contains two distinct integers s_j and t_j (1 ≤ s_j, t_j ≤ n, s_j ≠ t_j) — indices of nodes for j-th query.
  
  Output
  
  Print q lines. The j-th line should contain one integer: the minimum number of new nodes you create in order to move from a_{s_j} to a_{t_j}.
  
  Examples
  
  Input
  
  
  3 3
  2 10 3
  1 2
  1 3
  2 3
  
  
  Output
  
  
  0
  1
  1
  
  
  Input
  
  
  5 12
  3 8 7 6 25
  1 2
  1 3
  1 4
  1 5
  2 1
  2 3
  2 4
  2 5
  3 1
  3 2
  3 4
  3 5
  
  
  Output
  
  
  0
  1
  0
  1
  0
  1
  0
  1
  1
  1
  1
  2
  
  Note
  
  In the first example, you can first create new value 2 ⋅ 3 = 6 or 10 ⋅ 11 = 110 or 3 ⋅ 4 = 12. None of that is needed in the first query because you can already get from a_1 = 2 to a_2 = 10.
  
  In the second query, it's optimal to first create 6 or 12. For example, creating 6 makes it possible to get from a_1 = 2 to a_3 = 3 with a path (2, 6, 3).
  
  <image>
  
  In the last query of the second example, we want to get from a_3 = 7 to a_5 = 25. One way to achieve that is to first create 6 ⋅ 7 = 42 and then create 25 ⋅ 26 = 650. The final graph has seven nodes and it contains a path from a_3 = 7 to a_5 = 25.
solution: #include <bits/stdc++.h>
  class Scanner {
   private:
    static const int BUFFER_SIZE = 1 << 18;
    char buff[BUFFER_SIZE];
    char *buffPos, *buffLim;
    FILE* file;
  
   public:
    Scanner(FILE* file) {
      this->file = file;
      buffLim = buff + fread(buff, 1, BUFFER_SIZE, file);
      buffPos = buff;
    }
  
   private:
    inline void flushBuff() {
      buffLim = buff + fread(buff, 1, BUFFER_SIZE, file);
      if (buffLim == buff) {
        *buffLim++ = '\n';
      }
      buffPos = buff;
    }
    inline bool isWS(char t) { return t <= ' '; }
    inline bool isDig(char t) { return t >= '0' && t <= '9'; }
    inline void nextPos() {
      buffPos++;
      if (buffPos == buffLim) {
        flushBuff();
      }
    }
  
   public:
    inline char getchar() {
      char ch = *buffPos;
      nextPos();
      return ch;
    }
    inline void next(char* s) {
      while (isWS(*buffPos)) {
        nextPos();
      }
      while (!isWS(*buffPos)) {
        *s = *buffPos;
        s++;
        nextPos();
      }
      *s = '\0';
    }
    inline void nextLine(char* s) {
      while (*buffPos != '\n') {
        nextPos();
      }
      if (*buffPos == '\n') {
        nextPos();
      }
      while (*buffPos != '\n') {
        *s++ = *buffPos;
        nextPos();
      }
      *s = '\0';
    }
    inline int nextInt() {
      while (!isDig(*buffPos) && *buffPos != '-') {
        nextPos();
      }
      int sign = (*buffPos == '-') ? nextPos(), -1 : 1;
      int res = 0;
      while (isDig(*buffPos)) {
        res = res * 10 + *buffPos - '0';
        nextPos();
      }
      return res * sign;
    }
    inline long long nextLong() {
      while (!isDig(*buffPos) && *buffPos != '-') {
        nextPos();
      }
      long long sign = (*buffPos == '-') ? nextPos(), -1 : 1;
      long long res = 0;
      while (isDig(*buffPos)) {
        res = res * 10 + *buffPos - '0';
        nextPos();
      }
      return res * sign;
    }
    inline int n() {
      while (*buffPos < '0' || *buffPos > '9') {
        buffPos++;
        if (buffPos == buffLim) {
          flushBuff();
        }
      }
      int res = 0;
      while (*buffPos >= '0' && *buffPos <= '9') {
        res = res * 10 + (*buffPos - '0');
        buffPos++;
        if (buffPos == buffLim) {
          flushBuff();
        }
      }
      return res;
    }
    inline long long nl() {
      while (*buffPos < '0' || *buffPos > '9') {
        buffPos++;
        if (buffPos == buffLim) {
          flushBuff();
        }
      }
      long long res = 0;
      while (*buffPos >= '0' && *buffPos <= '9') {
        res = res * 10 + (*buffPos - '0');
        buffPos++;
        if (buffPos == buffLim) {
          flushBuff();
        }
      }
      return res;
    }
    inline long long nlm(const int MOD) {
      while (*buffPos < '0' || *buffPos > '9') {
        buffPos++;
        if (buffPos == buffLim) {
          flushBuff();
        }
      }
      long long res = 0;
      while (*buffPos >= '0' && *buffPos <= '9') {
        res = (res * 10 + (*buffPos - '0')) % MOD;
        buffPos++;
        if (buffPos == buffLim) {
          flushBuff();
        }
      }
      return res;
    }
    inline double nextDouble() {
      while (isWS(*buffPos)) {
        nextPos();
      }
      int sign = (*buffPos == '-') ? nextPos(), -1 : 1;
      double res = 0;
      while (isDig(*buffPos)) {
        res = res * 10 + *buffPos - '0';
        nextPos();
      }
      if (*buffPos == '.') {
        nextPos();
        double ep = 1;
        while (isDig(*buffPos)) {
          ep *= 0.1;
          res += ep * (*buffPos - '0');
          nextPos();
        }
      }
      return sign * res;
    }
    inline char nextChar() {
      while (isWS(*buffPos)) nextPos();
      char res = *buffPos;
      nextPos();
      return res;
    }
    ~Scanner() { fclose(file); }
  };
  Scanner sc(stdin);
  template <class __TyFirst, class __TySecond>
  std::ostream& operator<<(std::ostream& out,
                           const std::pair<__TyFirst, __TySecond>& o);
  static std::string cout_list_sep = " ";
  template <
      class IterateType, typename = decltype(std::declval<IterateType>().begin()),
      typename = decltype(std::declval<IterateType>().end()),
      typename = typename std::enable_if<std::is_convertible<
          typename std::iterator_traits<
              typename IterateType::iterator>::iterator_category,
          std::input_iterator_tag>::value>::type,
      typename = typename std::enable_if<!std::is_base_of<
          std::string, typename std::decay<IterateType>::type>::value>::type,
      typename value_type = typename IterateType::value_type>
  std::ostream& operator<<(std::ostream& out, const IterateType& a) {
    for (const auto& i : a) out << i << cout_list_sep;
    return out;
  }
  template <class __TyFirst, class __TySecond>
  std::ostream& operator<<(std::ostream& out,
                           const std::pair<__TyFirst, __TySecond>& o) {
    out << "(" << o.first << "," << o.second << ")";
    return out;
  }
  template <typename _ForwardIterator>
  void logArray(_ForwardIterator, _ForwardIterator, const char* = 0) {}
  namespace Temps {
  template <typename _IntType>
  class RangeInt {
    static_assert(std::is_integral<_IntType>::value,
                  "RangeInt object must have integral value type");
  
   public:
    class iterator : public std::iterator<std::input_iterator_tag, _IntType,
                                          _IntType, const _IntType*, _IntType> {
      _IntType val, step;
  
     public:
      using typename std::iterator<std::input_iterator_tag, _IntType, _IntType,
                                   const _IntType*, _IntType>::reference;
      explicit constexpr iterator(int val, int step) noexcept
          : val(val), step(step) {}
      constexpr iterator& operator++() noexcept {
        val += step;
        return *this;
      }
      constexpr iterator operator++(int) noexcept {
        iterator ret = *this;
        val += step;
        return ret;
      }
      constexpr bool operator==(const iterator& rhs) const noexcept {
        return val == rhs.val;
      }
      constexpr bool operator!=(const iterator& rhs) const noexcept {
        return val != rhs.val;
      }
      constexpr reference operator*() const { return val; }
    };
    const _IntType _begin, _step, _end;
    explicit constexpr RangeInt(const _IntType end) noexcept
        : _begin(0), _step(1), _end(end > 0 ? end : 0) {}
    explicit constexpr RangeInt(const _IntType begin, const _IntType end) noexcept
        : _begin(begin), _step(1), _end(end > begin ? end : begin) {}
    explicit constexpr RangeInt(const _IntType begin, const _IntType end,
                                const _IntType step)
        : _begin(begin),
          _step(step),
          _end(((step > 0 && end <= begin) || (step < 0 && end >= begin))
                   ? begin
                   : (step > 0
                          ? begin + (end - begin + step - 1) / step * step
                          : begin + (begin - end - step - 1) / (-step) * step)) {}
    constexpr iterator begin() const noexcept { return iterator(_begin, _step); }
    constexpr iterator end() const noexcept { return iterator(_end, _step); }
    constexpr _IntType size() const noexcept { return (_end - _begin) / _step; }
  };
  template <class IntType, typename = typename std::enable_if<
                               std::is_integral<IntType>::value>::type>
  inline constexpr RangeInt<IntType> range(IntType arg1) {
    return RangeInt<IntType>(arg1);
  }
  template <class IntType, typename = typename std::enable_if<
                               std::is_integral<IntType>::value>::type>
  inline constexpr RangeInt<IntType> range(IntType arg1, IntType arg2) {
    return RangeInt<IntType>(arg1, arg2);
  }
  template <class IntType, typename = typename std::enable_if<
                               std::is_integral<IntType>::value>::type>
  inline constexpr RangeInt<IntType> range(IntType arg1, IntType arg2,
                                           IntType arg3) {
    return RangeInt<IntType>(arg1, arg2, arg3);
  }
  }  // namespace Temps
  using Temps::range;
  namespace Temps {
  template <class T>
  inline bool checkMin(T& a, T b) {
    return (b < a ? a = b, 1 : 0);
  }
  template <class T>
  inline bool checkMax(T& a, T b) {
    return (a < b ? a = b, 1 : 0);
  }
  template <class IntType, typename = typename std::enable_if<
                               std::is_integral<IntType>::value>::type>
  IntType gcd(const IntType a, const IntType b) {
    return b == 0 ? a : gcd(b, a % b);
  }
  template <class IntType, typename = typename std::enable_if<
                               std::is_integral<IntType>::value>::type>
  IntType lcm(const IntType a, const IntType b) {
    return a / gcd(a, b) * b;
  }
  template <class ForwardIterator, class OutputIterator>
  void dissociate(ForwardIterator __begin, ForwardIterator __end,
                  OutputIterator __dest) {
    std::vector<typename std::iterator_traits<ForwardIterator>::_IntType> values(
        __begin, __end);
    std::sort(values.begin(), values.end());
    std::unique(values.begin(), values.end());
    while (__begin != __end) {
      *__dest =
          static_cast<typename std::iterator_traits<OutputIterator>::_IntType>(
              std::distance(
                  values.begin(),
                  std::lower_bound(values.begin(), values.end(), *__begin)));
      __dest++;
      __begin++;
    }
  }
  }  // namespace Temps
  using Temps::checkMax;
  using Temps::checkMin;
  namespace Temps {
  template <class Type>
  class Vector {
    static_assert(std::is_trivial<Type>::value,
                  "Temps::Vector can only be used for trival types");
  
   public:
    typedef Type& reference;
    typedef const Type& const_reference;
    class iterator : public std::iterator<std::random_access_iterator_tag, Type> {
     public:
      friend class Vector;
      using typename std::iterator<std::random_access_iterator_tag,
                                   Type>::difference_type;
      using
          typename std::iterator<std::random_access_iterator_tag, Type>::pointer;
      using typename std::iterator<std::random_access_iterator_tag,
                                   Type>::reference;
  
     private:
      pointer ptr;
      iterator(pointer ptr) : ptr(ptr) {}
  
     public:
      bool operator==(const iterator rhs) const { return ptr == rhs.ptr; }
      bool operator!=(const iterator rhs) const { return ptr != rhs.ptr; }
      bool operator<(const iterator rhs) const { return ptr < rhs.ptr; }
      bool operator<=(const iterator rhs) const { return ptr <= rhs.ptr; }
      bool operator>(const iterator rhs) const { return ptr > rhs.ptr; }
      bool operator>=(const iterator rhs) const { return ptr >= rhs.ptr; }
      iterator operator++() { return iterator(++ptr); }
      iterator operator++(int) { return iterator(ptr++); }
      iterator operator--() { return iterator(--ptr); }
      iterator operator--(int) { return iterator(ptr--); }
      iterator operator+(const difference_type dif) const {
        return iterator(ptr + dif);
      }
      iterator operator-(const difference_type dif) const {
        return iterator(ptr - dif);
      }
      iterator operator+=(const difference_type dif) {
        ptr += dif;
        return *this;
      }
      iterator operator-=(const difference_type dif) {
        ptr -= dif;
        return *this;
      }
      difference_type operator-(const iterator& rhs) const {
        return ptr - rhs.ptr;
      }
      operator pointer() { return ptr; }
    };
  
   protected:
    Type* a = nullptr;
    unsigned int _capacity = 0, _size = 0;
    void __grow_capacity(unsigned int least_size) {
      if (_capacity >= least_size) {
        return;
      }
      if (_capacity == 0) {
        _capacity = 1;
      }
      while (_capacity < least_size) {
        _capacity = _capacity * 2;
      }
      a = static_cast<Type*>(realloc(a, sizeof(Type) * _capacity));
    }
  
   public:
    Vector() = default;
    explicit Vector(unsigned int size, const Type& initial_value = Type())
        : _capacity(size), _size(size) {
      a = static_cast<Type*>(malloc(sizeof(Type) * _capacity));
      Type *__first = a, *const __last = a + _size;
      while (__first != __last) {
        *__first++ = initial_value;
      }
    }
    Vector(const Vector& rhs) : _capacity(rhs._size), _size(rhs._size) {
      a = static_cast<Type*>(malloc(sizeof(Type) * _capacity));
      Type *__first = a, *__r_p = rhs.a, *const __last = a + _size;
      while (__first != __last) {
        *__first++ = *__r_p++;
      }
    }
    Vector(Vector&& rhs) : _capacity(rhs._capacity), _size(rhs._size) {
      a = rhs.a;
      rhs.a = nullptr;
    }
    Vector(const std::initializer_list<Type>& list)
        : _capacity(
              static_cast<unsigned int>(std::distance(list.begin(), list.end()))),
          _size(_capacity) {
      a = static_cast<Type*>(malloc(sizeof(Type) * _capacity));
      Type* p = a;
      for (const auto& i : list) {
        *p++ = i;
      }
    }
    template <typename Container,
              typename = decltype(std::declval<Container>().begin(),
                                  std::declval<Container>().end())>
    Vector(const Container& list)
        : _capacity(
              static_cast<unsigned int>(std::distance(list.begin(), list.end()))),
          _size(_capacity) {
      a = static_cast<Type*>(malloc(sizeof(Type) * _capacity));
      Type* p = a;
      for (const auto& i : list) {
        *p++ = i;
      }
    }
    template <
        typename _InputIterator,
        typename = typename std::enable_if<std::is_convertible<
            typename std::iterator_traits<_InputIterator>::iterator_category,
            std::input_iterator_tag>::value>::type>
    explicit Vector(_InputIterator __first, _InputIterator __last) {
      _size = _capacity =
          static_cast<unsigned int>(std::distance(__first, __last));
      a = static_cast<Type*>(malloc(sizeof(Type) * _capacity));
      Type* p = a;
      while (__first != __last) {
        *p++ = *__first++;
      }
    }
    inline bool empty() const { return _size == 0; }
    inline unsigned int size() const { return _size; }
    inline unsigned int capacity() const { return _capacity; }
    void reserve(unsigned int __capacity) {
      _capacity = __capacity;
      if (_size > _capacity) {
        _size = _capacity;
      }
      a = static_cast<Type*>(realloc(a, sizeof(Type) * _capacity));
    }
    void resize(unsigned int __size) {
      if (_size > __size) {
        _size = __size;
        return;
      }
      __grow_capacity(__size);
      Type *__un = a + _size, *const __ed = a + __size;
      while (__un != __ed) {
        *__un++ = Type();
      }
      _size = __size;
    }
    inline void clear() { resize(0); }
    Vector& operator=(const Vector& rhs) {
      __grow_capacity(rhs._size);
      _size = rhs._size;
      Type* __first = a;
      const Type *const __last = a + _size, *__r_p = rhs.a;
      while (__first != __last) {
        *__first++ = *__r_p++;
      }
      return *this;
    }
    Vector& operator=(Vector&& rhs) {
      _size = rhs._size;
      _capacity = rhs._capacity;
      free(a);
      a = rhs.a;
      rhs.a = nullptr;
      return *this;
    }
    Type operator[](const unsigned int id) const { return a[id]; }
    Type& operator[](const unsigned int id) { return a[id]; }
    Type front() const { return a[0]; }
    Type& front() { return a[0]; }
    Type back() const { return a[_size - 1]; }
    Type& back() { return a[_size - 1]; }
    void pop_back() { _size--; }
    Vector& push_back(const Type& b) {
      __grow_capacity(_size + 1);
      a[_size] = b;
      _size++;
      return *this;
    }
    Vector& push_back(const Vector& rhs) {
      __grow_capacity(_size + rhs._size);
      for (const auto& i : rhs) {
        a[_size++] = i;
      }
      return *this;
    }
    Vector& push_back(const std::initializer_list<Type>& rhs) {
      __grow_capacity(_size + rhs.size());
      for (const auto& i : rhs) {
        a[_size++] = i;
      }
      return *this;
    }
    inline iterator begin() const { return iterator(a); }
    inline iterator end() const { return iterator(a + _size); }
    ~Vector() { free(a); }
  };
  }  // namespace Temps
  using Temps::Vector;
  void preInit();
  void init();
  void solve();
  int32_t main() {
    preInit();
    init();
    solve();
    return 0;
  }
  constexpr int N = 150005;
  constexpr int W = 1000005;
  bool is_prime[W];
  int min_fac[W];
  std::vector<int> primes;
  int n, q, a[N];
  void preInit() {
    memset(is_prime, true, sizeof(is_prime));
    for (int i = 2; i < W; i++) {
      if (is_prime[i]) {
        primes.push_back(i);
        min_fac[i] = i;
      }
      for (int j : primes) {
        int k = i * j;
        if (k >= W) break;
        is_prime[k] = false;
        min_fac[k] = j;
        if (i % j == 0) break;
      }
    }
  }
  struct Dsu {
    int p[W];
    Dsu() {
      for (int i = 0; i < W; i++) p[i] = i;
    }
    int get(int u) { return u == p[u] ? u : p[u] = get(p[u]); }
    void merge(int u, int v) { p[get(u)] = get(v); }
  } st;
  std::set<int> e[W];
  void init() {
    n = sc.n();
    q = sc.n();
    for (int i = 0; i < n; i++) a[i] = sc.n();
    for (int i = 0; i < n; i++) {
      int p = a[i];
      while (p != 1) {
        st.merge(a[i], min_fac[p]);
        p /= min_fac[p];
      }
    }
    auto link = [](int u, int v) {
      e[u].insert(v);
      e[v].insert(u);
    };
    for (int i = 0; i < n; i++) {
      int p = a[i] + 1, u = st.get(a[i]);
      std::vector<int> facs;
      while (p != 1) {
        facs.push_back(min_fac[p]);
        p /= min_fac[p];
      }
      for (int f : facs) link(u, st.get(f));
      for (size_t i = 0; i < facs.size(); i++)
        for (size_t j = i + 1; j < facs.size(); j++)
          link(st.get(facs[i]), st.get(facs[j]));
    }
  }
  void solve() {
    for (int i = 0; i < q; i++) {
      int s = st.get(a[sc.n() - 1]), t = st.get(a[sc.n() - 1]);
      if (s == t) {
        puts("0");
      } else {
        puts(e[s].count(t) ? "1" : "2");
      }
    }
  }
  