표

$n \times m$개의 칸으로 이루어진 직사각형 표를 생각하자. 각 칸은 검은색 또는 흰색으로 칠할 수 있다. 어떤 칸 네 개의 중심이 표의 변에 평행한 변을 가진 비퇴화 직사각형의 꼭짓점에 위치하면서 네 칸이 모두 같은 색인 경우가 없으면 그 색칠을 올바른 색칠이라고 한다.

직사각형의 서로 다른 올바른 색칠의 수를 구해야 한다. 이 수가 클 수 있으므로 주어진 모듈로 $r$로 나눈 나머지를 출력한다.

예를 들어 $2 \times 2$ 직사각형에서 이러한 색칠의 수는 14이다. 네 칸이 모두 한 가지 색으로 칠해진 색칠만 빼고 모두 해당한다.

첫째 줄에 테스트의 수 $t$가 주어진다. ($1 \le t \le 150$)

다음 $t$개 줄에 각각 정수 3개 $n$, $m$, $r$이 주어진다. $n$, $m$은 표의 크기이고 $r$은 답을 출력할 모듈로이다. ($1 \le n, m, r \le 10^{18}$)

각 테스트에 대해 답을 한 줄에 하나씩 출력한다.