$\lfloor b^n/a\rfloor$을 소수 $p$로 나눈 나머지를 구하는 프로그램을 작성하시오.

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\leq T\leq500)$

두 번째 줄부터 $T+1$번째 줄까지 정수 $a, b, n, p$가 주어진다. ($1\leq n\leq10^{18}, 1\leq a<b<p\leq10^9+7$, $p$는 소수)

각 테스트 케이스마다, $\lfloor b^n/a\rfloor$을 소수 $p$로 나눈 나머지를 출력한다.