This page is still under construction.

Parts of this page are still being built. What you see may change.

Bar Arrangement

Time limit1sMemory limit256 MB

Summary
Count permutations of 1 to n with exactly l left-to-right maxima and r right-to-left maxima for each test case.
Level

Medium6 of 10

Topics
Dynamic programming, Combinatorics
Solved
No attempts yet

Problem

There are nn bars of heights 1,2,…,n1, 2, \dots, n placed in a row. When you look at the bars from the left or from the right, a taller bar hides any shorter bar behind it. Consider the two arrangements of 44 bars shown below.

In both arrangements, exactly 11 bar is visible from the left and exactly 22 bars are visible from the right.

Given the number of bars nn, the number of bars ll visible from the left, and the number of bars rr visible from the right, write a program that counts how many arrangements produce this result.

Input

The first line contains the number of test cases TT. Each test case consists of a single line with three integers nn, ll, and rr. (1≤l,r≤n≤201 \le l, r \le n \le 20)

Output

For each test case, print the number of arrangements corresponding to the given nn, ll, and rr, one per line.

Examples1

  1. Example 1

    Input
    4
    4 1 2
    4 1 1
    5 2 4
    20 2 1
    
    Expected output
    2
    0
    4
    6402373705728000