#include <bits/stdc++.h>
using namespace std;
long long modpow(long long x, long long pot, long long mod) {
  long long t = x, res = 1;
  for (; pot; pot >>= 1) {
    if (pot & 1) res = res * t % mod;
    t = t * t % mod;
  }
  return res;
}
int P[32000], A[32000], cnt = 0;
void criba() {
  for (int i = 2; i < 32000; i++) {
    if (!A[i]) P[A[i] = ++cnt] = i;
    for (int j = 1; j <= A[i] && i * P[j] < 32000; j++) A[i * P[j]] = j;
  }
}
int phi(int x) {
  int res = 1;
  for (int i = 1; i < cnt + 1; i++)
    if (x % P[i] == 0) {
      int p = P[i], mul = p - 1;
      x /= p;
      for (; x % p == 0; x /= p) mul *= p;
      res *= mul;
    }
  if (x > 1) res *= x - 1;
  return res;
}
int T;
long long k, l, r, p;
int main() {
  ios_base::sync_with_stdio(0);
  cin >> T;
  while (T--) {
    cin >> k >> l >> r >> p;
    if (p == 2) {
      cout << (k % 2 ? 0 : 1) << endl;
    } else {
      long long prod;
      long long dl = modpow(2, l, p - 1);
      long long kl;
      if (l * log(2) < log(p - 1) - (1e-9))
        kl = modpow(k, dl, p);
      else
        kl = modpow(k, dl + p - 1, p);
      if (kl == 1)
        prod = modpow(2, r - l + 1, p);
      else {
        r++;
        long long dr = modpow(2, r, p - 1);
        long long kr;
        if (r * log(2) < log(p - 1) - (1e-9))
          kr = modpow(k, dr, p);
        else
          kr = modpow(k, dr + p - 1, p);
        prod = (kr - 1) * modpow(kl - 1, p - 2, p);
        prod = (prod % p + p) % p;
        r--;
      }
      if (k % 2) prod = prod * modpow(p / 2 + 1, r - l, p) % p;
      cout << prod << endl;
    }
  }
}
