Problem Description

A positive integer sequence A is considered good if and only if the following conditions are satisfied:

1. The length of A equals to n.
2. Suppose that k is the maximum value of A, A should contain [1,2,3...k-1,k] as a subsequence.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

First, Pty wants to know the number of good sequences.

Second, for each integer x ∈ [1,n], Pty also wants to know the occurrence number of x in all good sequences.

Since the answers might be very large, print the answers modulo p.

There are T test cases in total.

Input

The first line contains a single integer T(1 ≤ T ≤ 10) — the number of test cases.

For each test case, only one line contains two integers n,p (1 ≤ n ≤ 3000,1 ≤ p ≤ $10^9$).

Output

For each test case, output two lines.

The first line contains a integer - the number of good sequences modulo p.

The second line contains n integers separated by spaces-The $x^{th}$ integer represent the occurrence number of x in all good sequences modulo p.

2
3 3
3 1216

0
1 1 1
6
10 7 1