There are students in a classroom, out of which of them are girls. The teacher, Mr X wants to arrange all the students in a line. X thinks that his class girls are very talkative. So he doesn't want any two girls to be together. Mr X wants to know the number of ways he can arrange these students. Help him out.
The first line contains a single integer , denoting the number of testcases. Each of the next lines contain two integers and .
For each test case print the answer modulo in a single line.