# ZeroJudge - d271: 11582 - Colossal Fibonacci Numbers!
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=d271
###### tags: `ZeroJudge` `數學` `數論`

#include <iostream>
using namespace std;

unsigned long long buffer, power;
int pisano[1001] = { -1, 1 }, times, MOD, base, terms;

void Initialize() {
	int first, second, third, terms;
	for (int i = 2; i <= 1000; ++i) {
		first = terms = 0; second = 1;
		do {
			third = (first + second) % i;
			first = second; second = third;
			++terms;
		} while (first != 0 || second != 1);
		pisano[i] = terms;
	}
}

int FastPowers() {
	int answer = 1, buffer = base;
	while (power) {
		if (power & 1)
			answer = (answer * buffer) % pisano[MOD];
		buffer = (buffer * buffer) % pisano[MOD];
		power >>= 1;
	}
	return answer;
}

int FastFibonnacci() {
	terms = FastPowers();
	int answer[2][2] = { { 1, 0 }, { 0, 1 } }, matrix[2][2] = { { 0, 1 }, { 1, 1 } }, buffer[2][2];
	while (terms) {
		if (terms & 1) {
			for (int i = 0; i < 2; ++i)
				for (int j = 0; j < 2; ++j) {
					buffer[i][j] = 0;
					for (int k = 0; k < 2; ++k)
						buffer[i][j] = (buffer[i][j] + answer[i][k] * matrix[k][j]) % MOD;
				}
			for (int i = 0; i < 2; ++i)
				for (int j = 0; j < 2; ++j)
					answer[i][j] = buffer[i][j];
		}
		for (int i = 0; i < 2; ++i)
			for (int j = 0; j < 2; ++j) {
				buffer[i][j] = 0;
				for (int k = 0; k < 2; ++k)
					buffer[i][j] = (buffer[i][j] + matrix[i][k] * matrix[k][j]) % MOD;
			}
		for (int i = 0; i < 2; ++i)
			for (int j = 0; j < 2; ++j)
				matrix[i][j] = buffer[i][j];
		terms >>= 1;
	}
	return answer[0][1];
}

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	Initialize();
	cin >> times;
	while (times--) {
		cin >> buffer >> power >> MOD;
		base = buffer % pisano[MOD];
		cout << FastFibonnacci() << '\n';
	}
}