Треугольник Негодяй
Определение треугольника Раскала напоминает треугольник Паскаля. Строки нумеруются сверху, начиная с 0. Каждая строка n содержит n+1 чисел, индексированных от 0 до n. Обозначим R(n,m) как элемент с индексом m в строке с индексом n:
R(n,m) = 0 для n < 0 ИЛИ m < 0 ИЛИ m > n
Первое и последнее числа в каждой строке (которые совпадают в верхней строке) равны 1:
R(n,0) = R(n,n) = 1
Внутренние значения определяются по формуле (UpLeftEntry*UpRightEntry+1)/UpEntry (см. параллелограмм в массиве ниже):
R(n+1, m+1) = (R(n,m) * R(n,m+1) + 1)/R(n-1,m)
Напишите программу, которая вычисляет элемент R(n,m) в строке треугольника Раскала.
Входные данные
Первая строка входных данных содержит одно целое число P (1 ≤ P ≤ 1000), которое обозначает количество наборов данных, следующих далее. Каждый набор данных представлен одной строкой входных данных, состоящей из 3 десятичных целых чисел, разделенных пробелами. Первое число — номер набора данных, N. Второе число — номер строки n, и третье число — индекс m в строке, для которого вы должны найти элемент треугольника Раскала R(n,m) (0 ≤ m ≤ n ≤ 50000).
Выходные данные
Для каждого набора данных выведите одну строку. Она должна содержать номер набора данных N, за которым следует один пробел, а затем элемент треугольника Раскала R(n,m), округленный до целого значения.