#include <bits/stdc++.h>

int pd[100000+1] = {0};
int a[100000];
int prev[100000][18];
int lastpos[100000+1] = {0};
int pcnt[100000+1]= {0};
void fpd()
{
  for(int i = 2; i <= 100000; i++)
    {
      if (pd[i] == 0)
	{
	  pd[i] = i;
	  for(int j = i; j <= 100000; j += i)
	    pd[j] = i;
	}
    }
}
std::vector<int> getps(int n)
{
  std::vector<int> ans;
  while (n > 1)
    {
      int p = pd[n];
      ans.push_back(p);
      while (n % p == 0)
	{
	  n /= p;
	}
    }
  return ans;
}
int goback(int i, int n)
{
  int pos = i;
  int pow = 0;
  while (n)
    {
      if (pos == -1) return pos;
      if (n & 1)
	{
	  pos = prev[pos][pow];
	}
      pow++;
      n >>= 1;
    }
  return pos;
}


void add(int i)
{
  auto ps = getps(a[i]);
  for(auto p : ps)
    {pcnt[p]++;lastpos[p] = i;}
}

void rem(int i)
{
  auto ps = getps(a[i]);
  for(auto p : ps) pcnt[p]--;
}

void setprev(int i, int pr)
{
  prev[i][0] = pr;
  for(int p = 1; p <= 17; p++)
    {
      if (prev[i][p-1] == -1)
	prev[i][p] = -1;
      else
	prev[i][p] = prev[prev[i][p-1]][p-1];
    }
}
int first_out(int i, int lb)
{
  int l = 1;
  int h = i + 1;
  int ans = -1;
  while (l <= h)
    {
      int mid = (l + h) / 2;
      if (goback(i, mid) < lb)
	{
	  ans = mid;
	  h = mid - 1;
	}
      else
	{
	  l = mid + 1;
	}
    }
  return ans;
}

int main()
{
  for(int i = 0; i < 100000; i++)
    for(int p = 0; p <= 18; p++)
      prev[i][p] = -1;
  for(int i = 0; i <= 100000; i++)
    lastpos[i] = -1;
  fpd();
  int n, q;
  std::cin >> n >> q;
  std::vector<int> ans(q);
  std::vector<std::vector<std::pair<int, int>>> left(n);
  for(int i = 0; i < n; i++)
    std::cin >> a[i];
  for(int i = 0; i < q; i++)
    {
      int l, r;
      std::cin >> l >> r;
      l--, r--;
      left[r].push_back({l, i});
    }
  int j = 0;
  for(int i = 0; i < n; i++)
    {
      auto ps = getps(a[i]);
      int maxlastpos = -1;
      for(auto p : ps)
	{
	  if (pcnt[p])
	    {
	      maxlastpos = std::max(maxlastpos, lastpos[p]);
	    }
	}
      add(i);
      if (maxlastpos != -1)
	{
	  while (j <= maxlastpos)
	    {
	      rem(j);
	      j++;
	    }
	}
      setprev(i, j - 1);
      for(auto[l, qi] : left[i])
	{
	  ans[qi] = first_out(i, l);
	}
    }
  for(auto a : ans)
    std::cout << a << "\n";
}
