F.A.Q
Hand In Hand
Online Acmers
Forum | Discuss
Statistical Charts
Problem Archive
Realtime Judge Status
Authors Ranklist

C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
Virtual Contests
DIY | Web-DIY beta
Recent Contests
Register new ID

# Crime

Time Limit: 60000/30000 MS (Java/Others)    Memory Limit: 655360/327680 K (Java/Others)
Total Submission(s): 708    Accepted Submission(s): 262

Problem Description
You kill a person and will be executed by shooting tomorrow,but you have a program contest to do today,after several hours' hard work,you solved all problems except this one.You died with the pity that didn't solved it.But now you have second chance.
Count the number of permutation of number 1 to n that every adjacent number are coprime.To avoid large number,output the result mod a number M.

Input
The first line contains integer T(1<=T<=5).Denoting the number of the test cases.
Then T lines follows,each line contains two integers n,M (1<=n<=28, 1<=M<=30000).
The n for each test cases will not be the same.

Output
For each test cases,print the answer in a line.

Sample Input
5
1 10000
2 10000
3 10000
4 10000
5 10000

Sample Output
1
2
6
12
72
Hint
There is a solution without making table.
Two integers are coprime if their greatest common divisor is 1.


Author
WJMZBMR

Source

Recommend
zhuyuanchen520

Statistic | Submit | Discuss | Note
 Home | Top Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2020 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.015600(s) query 2, Server time : 2020-01-25 07:24:36, Gzip enabled Administration