라스칼 삼각형

라스칼 삼각형은 파스칼 삼각형과 비슷한 규칙으로 만들어진다.

맨 위 줄을 0번째 줄이라고 한다. i번째 줄에는 i+1개의 수가 있으며, 왼쪽부터 0번째부터 i번째까지 번호가 붙는다. R(i, j)는 i번째 줄의 j번째 수를 뜻한다.

범위를 벗어난 위치는 0으로 둔다.

R(n, m) = 0 (n < 0 또는 m < 0 또는 m > n)

각 줄의 첫 번째 수와 마지막 수는 1이다.

R(n, 0) = R(n, n) = 1

나머지 수는 서쪽 값과 동쪽 값을 곱한 뒤 1을 더하고, 북쪽 값으로 나누어 구한다.

이를 식으로 쓰면 다음과 같다.

R(n+1, m+1) = (R(n, m) * R(n, m+1) + 1) / R(n-1, m)

주어진 n과 m에 대해 R(n, m)을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 <= T <= 1,000)

각 테스트 케이스는 한 줄에 두 정수 n과 m으로 주어진다. (0 <= m <= n <= 50,000)

각 테스트 케이스마다 R(n, m)을 한 줄에 하나씩 출력한다.