PERMUT1 - Permutations


Let A = [a1, a2, ... an] be a permutation of integers 1, 2, ... n. A pair of indices (i, j), 1 <= i <= j <= n, is an inversion of the permutation A if ai > aj. We are given integers n > 0 and k >= 0. What is the number of n-element permutations containing exactly k inversions?

For instance, the number of 4-element permutations with exactly 1 inversion equals 3.

Task

Write a program which for each data set from a sequence of several data sets:

  • reads integers n and k from input,
  • computes the number of n-element permutations with exactly k inversions,
  • writes the result to output.

Input

The first line of the input file contains one integer d, 1 <= d <= 10, which is the number of data sets. The data sets follow. Each data set occupies one line of the input file and contains two integers n (1 <= n <= 12) and k (0 <= k <= 98) separated by a single space.

Output

The i-th line of the output file should contain one integer - the number of n-element permutations with exactly k inversions.

Example

Input:
1
4 1

Output:
3

hide comments
poojan : 2016-03-08 15:38:29

Great Problem !Ac 1 go! Another DP for beginners! Great Feeling after solve This!

siva_spoj: 2015-11-08 16:58:42

Input constraints are not valid. Dont assume n can be maximum 12

xxbloodysantaxx: 2015-07-10 15:37:51

Don't make a mistake of dividing into two lengths and count there inversions seperately! It will miss out the cases of crossing inversions! Morover it is highly inefficient than the actual solution

PRIBAN91: 2015-06-09 12:44:44

Nice problem!

sobriquet: 2014-12-17 17:09:20

Good one.

shankar: 2014-09-08 15:19:52

WOW an easy one

Garima: 2014-08-15 11:35:06

Make sure your answer for 1 0 is 1.

ankg: 2014-06-27 22:48:00

Yo! First Dp! It's awesome! :D

tapopadma: 2014-06-26 21:06:45

VERY EG ! :)

nitesh kumar: 2014-06-02 06:16:41

nic 1.


Added by:adrian
Date:2004-06-22
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:III Polish Collegiate Team Programming Contest (AMPPZ), 1998