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}$.

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
:D: 2022-03-19 23:30:05

@subhashs "aaa" and "bbb" are not square strings, but they also not "prefix square free" and that's what we are counting in this problem.

subhashs: 2019-03-20 09:47:24

@zimpha: Quoting from problem statement "For example, "abab", "aa" are square strings, while "aaa", "abba" are not." Then why are "aaa" "bbb" not in the 8 strings you have mentioned for the first test case? Not sure i understand the problem.

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
Date:2018-01-02
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All