#include <bits/stdc++.h>
using namespace std;
long long pow(long long b, long long e, long long m) {
  long long t = 1;
  for (; e; e >>= 1, b = b * b % m) e & 1 ? t = t * b % m : 0;
  return t;
}
template <class T>
inline bool chkmin(T &a, T b) {
  return a > b ? a = b, true : false;
}
template <class T>
inline bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <class edge>
struct Graph {
  vector<vector<edge> > adj;
  Graph(int n) {
    adj.clear();
    adj.resize(n + 5);
  }
  Graph() { adj.clear(); }
  void resize(int n) { adj.resize(n + 5); }
  void add(int s, edge e) { adj[s].push_back(e); }
  void del(int s, edge e) { adj[s].erase(find(iter(adj[s]), e)); }
  int deg(int v) { return adj[v].size(); }
  vector<edge> &operator[](int t) { return adj[t]; }
};
const int maxr = 33;
pair<long long, long long> get_mod(int k, int m, int P, int r) {
  long long v[maxr] = {0}, u[maxr];
  for (int i = 0; i <= r; ++i) v[i] = k % P, k /= P;
  for (int i = 1; i <= m; ++i) {
    for (int x = 0; x <= r; ++x) u[x] = 0;
    for (int x = 0; x <= r; ++x) {
      long long s = 0;
      for (int y = 0; x + y <= r; ++y)
        s += v[x] * v[y] + u[x + y], u[x + y] = s % P, s /= P;
    }
    for (int x = 0; x <= r; ++x) v[x] = u[x];
  }
  assert(v[0] == 1);
  int lx = 1;
  for (; !v[lx] && lx < r; ++lx)
    ;
  return make_pair(v[lx], lx);
}
pair<long long, long long> calc(int k, long long R, int P) {
  cerr << "calc: " << k << " " << R << " " << P << endl;
  long long rem = pow(k, pow(2, R, P - 1), P);
  if (rem != 1) return make_pair(rem - 1, 0);
  long long w = 0;
  for (; 2 << w < P; ++w)
    ;
  pair<long long, long long> ret = make_pair(0, 0);
  for (int r = 1; ret.first == 0; r *= 2) ret = get_mod(k, min(w, R), P, r);
  ret.first = ret.first * pow(2, R - min(w, R), P);
  return ret;
}
int main() {
  ios_base::sync_with_stdio(false);
  int tc, k, P;
  long long L, R;
  cin >> tc;
  for (; tc--;) {
    long long ans;
    cin >> k >> L >> R >> P;
    if (k % P == 0)
      ans = 1;
    else if (k % P == 1)
      ans = pow(2, R - L + 1, P);
    else {
      pair<long long, long long> ansR = calc(k, R + 1, P), ansL = calc(k, L, P);
      if (ansL.second != ansR.second)
        ans = 0;
      else
        ans = ansR.first * pow(ansL.first, P - 2, P) % P;
    }
    if (k & 1) ans = ans * pow(2, (R - L) % (P - 1) * (P - 2) % (P - 1), P) % P;
    cout << ans << endl;
  }
  return 0;
}
