종이 띠 자르기

Hektor는 $2^{30} = 1073741824$개의 동일한 직사각형 칸으로 나뉜 긴 직사각형 종이 띠를 가지고 있습니다. 칸에는 왼쪽부터 차례대로 $1$번부터 자연수 번호가 매겨져 있습니다. Hektor는 이 띠를 더 작은 조각으로 자르려고 합니다. 그의 자르기는 항상 완벽해서, 자르는 띠의 정확히 한가운데를 지나갑니다. 또한 그는 길이가 한 칸인 띠는 절대 반으로 자르지 않습니다.

자르기를 모두 마친 뒤 Hektor는, 만들어진 조각들 중 몇 개를 나란히 붙이면 구간 $[a, b]$에 속한 번호들을 빈틈이나 겹침 없이 정확히 재현할 수 있음을 알게 되었습니다. 그는 다르게 잘랐다면 이 구간을 서로 다른 몇 가지 방법으로 재현할 수 있었을지 궁금합니다. 두 재현이 사용한 조각들의 집합이 다르면 서로 다른 재현으로 셉니다. 가능한 서로 다른 재현의 수를 구하도록 도와주세요.

첫 번째 줄에 테스트 케이스의 수 $Z$ ($1 \le Z \le 10$)가 주어집니다.

이어지는 $Z$개의 각 줄에는 세 정수 $a$, $b$, $m$ ($1 \le a \le b \le 1073741824$, $1 \le m \le 1000000$)이 주어집니다.

각 테스트 케이스마다 Hektor가 구간 $[a, b]$를 재현할 수 있는 서로 다른 방법의 수를 $m$으로 나눈 나머지를 한 줄에 하나씩 출력합니다.

$[2, 2]$를 정확히 재현하는 방법은 칸 $2$ 하나만을 나타내는 조각을 쓰는 단 한 가지뿐입니다.

$[3, 4]$는 두 가지 방법으로 재현할 수 있습니다. 구간 전체를 덮는 조각 $[3, 4]$ 하나를 쓰거나, 두 조각 $[3, 3]$과 $[4, 4]$를 씁니다.

$[1, 3]$도 두 가지 방법으로 재현할 수 있습니다. 세 조각 $[1, 1]$, $[2, 2]$, $[3, 3]$을 쓰거나, 두 조각 $[1, 2]$와 $[3, 3]$을 씁니다.