Untuk menentukan apakah pohon-pohon berakar bersifat isomorfik (pada soal ini, Anda tidak memerlukan pengetahuan awal tentang isomorfisme pohon), algoritma yang umum digunakan adalah tree hashing. Dengan fungsi hash yang sesuai, pohon berakar yang tidak isomorfik kemungkinan besar akan menghasilkan nilai hash yang berbeda, namun tabrakan hash (hash collision) juga sulit dihindari.

Terdapat berbagai implementasi fungsi hash, tetapi beberapa rancangan fungsi hash kurang tepat. Little C memiliki fungsi hash yang "kurang tepat" seperti itu, yang didefinisikan sebagai berikut: Misalkan $sz_x$ adalah banyaknya titik yang termuat di dalam upapohon dari $x$, dan $son_x$ adalah himpunan semua simpul anak dari $x$. Untuk sebuah pohon berakar dengan $r$ sebagai akarnya, nilai hash $h(r)$ didefinisikan sebagai:

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

dengan $f$ menyatakan pemetaan apa pun dari himpunan bilangan bulat positif ke himpunan bilangan bulat positif, yaitu $f \in \{\varphi : \mathbb{Z}^+ \to \mathbb{Z}^+\}$. Secara khusus, nilai hash untuk pohon berakar yang hanya memiliki satu simpul adalah $1$.

Selanjutnya, Little C mendefinisikan bahwa untuk dua pohon berakar, jika untuk semua pilihan $f$ tidak mungkin dihitung nilai hash yang berbeda, maka kedua pohon tersebut dikatakan tak dapat dibedakan (indistinguishable); sebaliknya, jika terdapat suatu pilihan $f$ sehingga kedua pohon dapat menghasilkan nilai hash yang berbeda, maka kedua pohon tersebut dikatakan dapat dibedakan (distinguishable).

Little C ingin menggunakan fungsi hash ini untuk membangkitkan sebanyak mungkin pohon biner berakar, yaitu pohon berakar yang setiap simpulnya memiliki paling banyak dua simpul anak. Little C berharap Anda dapat menghitung jumlah maksimum pohon biner berakar berisi $n$ simpul yang saling dapat dibedakan. Tentu saja jawabannya bisa sangat besar, sehingga Little C telah menyiapkan modulus $p$ untuk Anda, dan Anda perlu mengambil hasil akhirnya modulo $p$.

Masukan

Soal ini memuat beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10000$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, masukan terdiri dari satu baris tunggal dengan dua bilangan bulat $n, p$ ($1 \le n \le 3000, 2 \le p \le 10^9 + 9$), yang menyatakan banyaknya simpul pada pohon berakar dan modulus yang diberikan oleh Little C.

Dijamin bahwa jumlah total $n$ untuk seluruh kasus uji tidak melebihi $10000$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris berisi sebuah bilangan bulat yang menyatakan hasil jawaban modulo $p$.

Contoh

Contoh Masukan 1

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

Contoh Keluaran 1

1
6
207
10904
478868953
202933416
152259136
264735211