2015
04-14

# Harry Potter and the D.A.

D.A., short for Dumbledore’s Army, is found by Harry while fighting with Voldemort. In the last battle, the D.A. has contributed greatly to smashing the Death Eater. Before this, Harry Potter had trained them a lot about defensing against the Dark Arts.

For easy recognizing, each of the D.A. has a unique ID, from 1 to N. At ordinary time, they lined up by a certain order. But in Harry’s memory, there was one day they messed up, so he asked them to change their position. At first, he use the magic to remember all pairs, e.g. if the i-th ID is pi, Harry would commit the pair to memory. Then, in each round, he would require the pi-th magician to stand in the i-th place. By doing this again and again, after exactly K round, he found the ID sequence is the same as the original, and what’s more, it’s the first time they all come back!
But unfortunately, Harry can’t remember the ID sequence on that day, so he asks you for help, to calculate the number of permutations fitting this situation.

The first line contains a single integer T, indicating the number of test cases.
Each test case contains two integers, N and K.

Technical Specification

1. 1 <= T <= 50
2. 1 <= N <= 100
3. 1 <= K <= 1 000 000 000

The first line contains a single integer T, indicating the number of test cases.
Each test case contains two integers, N and K.

Technical Specification

1. 1 <= T <= 50
2. 1 <= N <= 100
3. 1 <= K <= 1 000 000 000

2
1 1
3 3

Case 1: 1
Case 2: 2

1. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.