"Palindromes are the worst..."
Little Q hates palindromes of any kind:
(1) If a string reads the same forwards and backwards, Little Q hates it; for example, aa and aba.
(2) For a string, if removing a prefix and appending it to the end of the string results in a string that Little Q hates, then Little Q also hates the original string; for example, aab and baa.
The question is: if any string can only be composed of $k$ known characters, how many strings of length $n$ are hated by Little Q?
The answer may be very large, so you only need to output the answer modulo $p$.
Input
The first line contains a positive integer $T$, representing the number of test cases.
The next $T$ lines each describe a test case, containing three positive integers $n$, $k$, and $p$.
Output
For each test case, output one line containing an integer representing the answer modulo $p$.
Examples
Input 1
10 1 1 1000000001 2 2 1000000003 3 2 1000000005 3 3 1000000007 4 2 1000000009 4 3 1000000011 4 4 1000000013 5 5 1000000015 7 7 1000000017 9 9 1000000019
Output 1
1 2 8 21 6 15 28 605 16765 530937
Input 2
10 8821612800 758922381 1073365919 8380532160 166822173 1001828119 9311702400 7367823578 1015387267 6983776800 1646145481 1030885259 6692786100 1953515781 1073365919 7138971840 2649942813 1001828119 6469693230 2585876408 1015387267 8031343320 1646145481 1030885259 9995200351 645412247 1030328983 9302162851 1649517328 1053299347
Output 2
896784901 911577797 674524325 392648220 646549222 879297585 384496639 889650008 957785169 413147483
Note
For 30% of the data, $1 \le n \le 10^{10}$.
For 60% of the data, $1 \le n \le 10^{14}$.
For 100% of the data, $1 \le T \le 10$, $1 \le n \le 10^{18}$, $1 \le k \le n$, $10^9 \le p \le 2^{30}$.