PSFWORDS  Prefix Square Free Words
A string is called a square string if it can be obtained by concatenating two copies of the same string (i.e. $s=uu$ for some word $u$). For example, "abab", "aa" are square strings, while "aaa", "abba" are not. A string is called prefixsquare free if none of its prefixes is a square.
Chiaki would like to know the number of nonempty prefixsquare free strings whose length is less than or equal to $n$. The size of the alphabet Chiaki uses is $m$. As this number may be very large, Chiaki is only interested in its remainder modulo $2^{32}$.
Input
There are multiple test cases. The first line of input contains an integer $T$ ($1 \le T \le 100$), indicating the number of test cases. For each test case:
The first line contains two integers $n$ and $m$ ($1 \le n \le 100, 1 \le m \le 10^9$)  the length of the string and the size of the alphabet.
Output
For each test case, output an integer denoting the answer.
Example
Input:
2 3 2 4 6
Output:
8 1266
Information
There are $5$ input files:
 Input #1: $1 \le T \le 100, 1 \le n \le 10$.
 Input #2: $1 \le T \le 50, 1 \le n \le 30$.
 Input #3: $1 \le T \le 30, 1 \le n \le 60$.
 Input #4: $1 \le T \le 10, 1 \le n \le 80$.
 Input #5: $1 \le T \le 2, 1 \le n \le 100$.
hide comments
zimpha:
20180106 04:16:33
@Shubhojeet Chakraborty For the first test case, there 8 strings: a, b, ab, ba, aba, abb, baa, bab. 

Shubhojeet Chakraborty:
20180105 06:48:06
Can someone explain the given test cases.thanks. 

zimpha:
20180104 13:03:43
@Min_25 thx, fixed. 

Min_25:
20180104 09:15:19
Not "the number of prefixsquare free strings of length n", but "the number of prefixsquare free strings of length <= n" ? 
Added by:  zimpha 
Date:  20180102 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 