RECFUN - Recursive function

no tags 

Alice loves mathematics. She recently got a laptop and so is excited to solve her crazy mathematics problems using her Lappy.

One day, she discovered something known as RecursiveSum. RecursiveSum is a recursive function defined as:

  1. RecursiveSum(0, n) = n, for all n > 0.
  2. RecursiveSum(k, n) = RecursiveSum(k - 1, 1) + RecursiveSum(k - 1, 2) + ... + RecursiveSum(k - 1, n), for all positive k, n.

She wants to make a program that can find recursive sum for any given pairs of k and n. She has no coding experience yet, so she wants you to solve this problem for her. Given k and n, your task is to write a code that can return the value for RecursiveSum(k, n).

Input

First line of input consists of an integer T <= 200 which is the number of test cases. Each test case consists of two integers k and n (1 <= k <= 14 and 1 <= n <= 14).

Output

For each test case, output a single line containing the integer RecursiveSum(k, n). The output is guaranteed to fit in 32-bit integer.

Example

Input:
4
1 3
5 1
4 10
8 6

Output:
6
1
2002
2002

hide comments
nadstratosfer: 2020-06-24 11:52:51

So, how did she discover RecursiveSum without coding it?...

I also like the algorithm of using the laptop to coerce, typically male, programmers, to do the exciting solving for her. This is a recurring pattern in problem statements, wondering if it's adolescent white knight fantasy or reflection on a real-life work in affirmative action-infested corporations..

dewa251202: 2018-09-10 18:39:23

Memoization!


Added by:Mahesh Chandra Sharma
Date:2011-01-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C CSHARP C++ 4.3.2 CPP C99 JAVA PHP PYTHON PYTHON3 RUBY SCALA
Resource:Based on a topcoder problem