MECGROUP - project groups

HOD of CSE Dept. of MMMEC, asked the students to form the groups for their final year project. He said that there will be t students per team and there will be at least 4 boys and at least 1 girl per group.

A curious student Rajesh want to know the total number of ways by which the groups can be made. Because he is busy in forming his group so you, write a program to find the total ways and help him.

Input

First line contains an integer n which itself indicates number of test cases.

Each test case comprises of three space separated integers "B G t". Where B denotes number of boys, G denotes number of girls in the class, and t denotes number of students in a group.

Constraints

1 <= n <= 20

4 <= B <= 30

1 <= G <= 30

5 <= t <= B + G

Output

For each test case print total number of ways per line.

Example

Input:
2
4 1 5
30 30 20

Output:
1
4191318957352590

Added by:bristy
Date:2012-01-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ADA95 ASM32 ASM64 GAWK BASH BF CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO HASK ICON ICK JS-RHINO LUA NEM NICE OCAML PERL PERL6 PHP PIKE PRLG-swi RUBY SCALA SCM guile SCM qobi SED ST TCL WHITESPACE
Resource:own

hide comments
2012-02-23 18:17:56 Mitch Schwartz
Are teams labelled or not? For example, when (B,G,t)=(8,2,5), would groupings

({B1,B2,B3,B4,G1}, {B5,B6,B7,B8,G2})
and
({B5,B6,B7,B8,G2}, {B1,B2,B3,B4,G1})

be considered the same or distinct? It's a little annoying to have to guess and see if the answer matches the second test case..

Edit: Nevermind, I think they should differ by a factor of ((B+G)/t)! so it's not an issue.

I don't suppose anyone else gets 96268980464138389301093700 for (30,30,20), with unlabelled groups? I have to assume that it's my own stupid mistake, since there are so many AC solutions..

But for (30,30,20), aren't there 96305202413079303971977650 ways to form unlabelled groups, if we ignore the restrictions that there must be at least 4 boys and at least 1 girl per group? If this is so, then adding the restrictions couldn't possibly cut down the number so much, as given in sample data. (Just think in terms of probability that a random grouping will satisfy the restrictions. I wrote a quick simulation, and it stays around the ratio of the two large numbers I gave here.) Hmm.

Edit: I explain my reasoning at https://www.spoj.pl/forum/viewtopic.php?f=3&t=10415 , if anyone wants to check it.

Last edit: 2012-01-16 00:34:45
2012-02-23 18:17:56 Efim
Please, allow other languages.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.