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 prefix-square free if none of its prefixes is a square.

Chiaki would like to know the number of nonempty prefix-square 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}$.


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.


For each test case, output an integer denoting the answer.



3 2
4 6




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: 2018-01-06 04:16:33

@Shubhojeet Chakraborty For the first test case, there 8 strings: a, b, ab, ba, aba, abb, baa, bab.

Shubhojeet Chakraborty: 2018-01-05 06:48:06

Can someone explain the given test cases.thanks.

zimpha: 2018-01-04 13:03:43

@Min_25 thx, fixed.

Min_25: 2018-01-04 09:15:19

Not "the number of prefix-square free strings of length n", but "the number of prefix-square free strings of length <= n" ?

Added by:zimpha
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)