Per determinare se degli alberi radicati sono isomorfi (in questo problema non sono richieste conoscenze preliminari sull'isomorfismo tra alberi), un algoritmo comune consiste nell'utilizzare il tree hashing. Con una funzione di hash adeguata, alberi radicati non isomorfi producono probabilmente valori di hash diversi, ma anche le collisioni di hash sono difficili da evitare.

Esistono varie implementazioni di funzioni di hash, ma alcuni progetti di funzioni di hash non sono del tutto corretti. Little C ha una di queste funzioni di hash «non molto corrette», definita come segue: sia $sz_x$ il numero di vertici contenuti nel sottoalbero di $x$, e $son_x$ l'insieme di tutti i nodi figli di $x$. Per un albero radicato con $r$ come radice, il suo valore di hash $h(r)$ è definito come:

$$h(r) = 1 + \sum_{v \in son_r} h(v) \times f(sz_v)$$

dove $f$ rappresenta una qualsiasi funzione dall'insieme degli interi positivi all'insieme degli interi positivi, ossia $f \in \{\varphi : \mathbb{Z}^+ \to \mathbb{Z}^+\}$. In particolare, il valore di hash per un albero radicato con un solo nodo è $1$.

Successivamente, Little C definisce che per due alberi radicati, se per tutte le scelte di $f$ è impossibile calcolare valori di hash diversi, allora i due alberi si dicono indistinguibili; altrimenti, se esiste una scelta di $f$ tale che i due alberi possano produrre valori di hash diversi, allora i due alberi si dicono distinguibili.

Little C vuole usare questa funzione di hash per generare il maggior numero possibile di alberi binari radicati, ovvero alberi radicati in cui ogni nodo ha al massimo due nodi figli. Little C spera che tu possa calcolare il numero massimo di alberi binari radicati distinguibili contenenti $n$ nodi. Naturalmente la risposta può essere molto grande, quindi Little C ha preparato per te un modulo $p$, e dovrai calcolare il risultato modulo $p$.

Input

Questo problema contiene più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 10000$), che rappresenta il numero di casi di test.

Per ciascun caso di test, l'input è costituito da una singola riga con due interi $n, p$ ($1 \le n \le 3000, 2 \le p \le 10^9 + 9$), che rappresentano il numero di nodi nell'albero radicato e il modulo fornito da Little C.

È garantito che la somma totale di $n$ per tutti i casi di test non superi $10000$.

Output

Per ciascun caso di test, stampa una singola riga con un intero, che rappresenta il risultato della risposta modulo $p$.

Esempio

Input di esempio 1

8
1 1000000009
5 1000000009
10 1000000009
15 1000000009
100 1000000009
150 1000000009
1000 1000000009
1500 1000000009

Output di esempio 1

1
6
207
10904
478868953
202933416
152259136
264735211