#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:65777216")
using namespace std;
long long qp(long long c, long long st, int mod) {
  long long r = 1;
  while (st) {
    if (st & 1) r = (r * c) % mod;
    c = (c * c) % mod;
    st >>= 1;
  }
  return r;
}
long long gcd(long long a, long long b) {
  if (a < 0) a = -a;
  if (b < 0) b = -b;
  while (a && b)
    if (a > b)
      a %= b;
    else
      b %= a;
  return a + b;
}
int solve(int k, long long l, long long r, int p) {
  if (p == 2) return 1 - (k % 2);
  int pw = qp(2, l, p - 1);
  int a = qp(k, pw, p);
  if (k % p == 0) a = 0;
  if (a == 1) {
    long long res = qp(2, r - l + 1, p);
    if (k % 2) {
      res *= qp(qp(2, r - l, p), p - 2, p);
      res %= p;
    }
    return res;
  }
  long long res = qp(a, qp(2, r - l + 1, p - 1), p);
  if (a == 0) res = 0;
  res--;
  if (res < 0) res += p;
  int aa = a - 1;
  if (aa < 0) aa += p;
  res *= qp(aa, p - 2, p);
  res %= p;
  if (k % 2) {
    res *= qp(qp(2, r - l, p), p - 2, p);
    res %= p;
  }
  return res;
}
int stupid(int k, long long l, long long r, int p) {
  int mod = 1000000007;
  long long res = 1;
  for (long long i = l; i <= r; i++) {
    long long st = qp(2, i, mod - 1);
    long long val = qp(k, st, mod) + 1;
    long long g = gcd(res, val);
    res = res / g * val;
  }
  return res % p;
}
int main() {
  int tc;
  cin >> tc;
  for (int TC(0); TC < (tc); TC++) {
    int k, p;
    long long l, r;
    scanf("%d %I64d %I64d %d", &k, &l, &r, &p);
    printf("%d\n", solve(k, l, r, p));
  }
  return 0;
}
