폴하버의 삼각형

1부터 n까지 m제곱의 합은 다음과 같다.

S(n,m) = SUM (j = i to n) (jm)

이 식은 n의 차수가 m+1인 다항식으로 나타낼 수 있다.

S(n,m) = SUM (k = 1 to m+1) (F(m,k) * nk)

예를 들면 다음과 같다.

S(n,1) = (1 + ... + n) = (1/2)*n2 + (1/2)*nS(n,2) = (1 + ... + n2) = (1/3)*n3 + (1/2)*n2 + (1/6)*nS(n,3) = (1 + ... + n3) = (1/4)*n4 + (1/2)*n3 + (1/4)*n2S(n,4) = (1 + ... + n4) = (1/5)*n5 + (1/2)*n4 + (1/3)*n3 - (1/30)*n

위의 식에 나오는 계수 F(m,k)는 폴하버의 삼각형을 이룬다.

F(m,k)에서 m은 행이고, 위에서부터 0번이다. k는 열이고, 왼쪽에서부터 1번이다.

폴하버의 삼각형은 아래와 같이 구할 수 있다.

1. j>1인 F(i,j) = (i/j)*F(i-1,j-1)
2. i번째 row의 수를 다 더했을 때 1이 되도록 F(i,1) 을 정해야 한다

m,k 가 주어졌을 때, F(m,k)를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 P (1 ≤ P ≤ 1000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, m과 k가 공백으로 구분되어져 있다. (0 ≤ m ≤ 400, 1 ≤ k ≤ n+1)

각 테스트 케이스에 대해서, F(m,k)를 출력한다. 만약 결과가 정수라면 정수로 출력하고, 정수가 아니라면, 기약분수로 출력한다.