Sphere Online Judge

SPOJ Problem Set (classical)

78. Marbles

Problem code: MARBLES


Hänschen dreams he is in a shop with an infinite amount of marbles. He is allowed to select n marbles. There are marbles of k different colors. From each color there are also infinitely many marbles. Hänschen wants to have at least one marble of each color, but still there are a lot of possibilities for his selection. In his effort to make a decision he wakes up. Now he asks you how many possibilites for his selection he would have had. Assume that marbles of equal color can't be distinguished, and the order of the marbles is irrelevant.

Input

The first line of input contains a number T <= 100 that indicates the number of test cases to follow. Each test case consists of one line containing n and k, where n is the number of marbles Hänschen selects and k is the number of different colors of the marbles. You can assume that 1<=k<=n<=1000000.

Output

For each test case print the number of possibilities that Hänschen would have had. You can assume that this number fits into a signed 64 bit integer.

Example

Input:
2
10 10
30 7

Output:
1
475020

Added by:Adrian Kuegel
Date:2004-06-19
Time limit:0.248s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: NODEJS PERL 6
Resource:own problem

hide comments
2014-09-11 09:49:40 Arun Karthikeyan
stars and bars saved my ass with this one :P
2014-08-29 13:16:22 Anubhav Balodhi
A simple question with mathematical programming :-D
2014-07-17 17:53:42 Saurabh Goyal
stars and bars...
2014-07-03 11:52:30 Kruti K Mohanta
TLE if not written:-

if (k < 0 || k > n) return 0;
if (n-k < k) k = n-k;
2014-06-19 19:08:20 ANKIT KUMAR
can any one say me why my soln is giving me segmentation fault .... plz here is my soln http://www.spoj.com/submit/MARBLES/id=11790045
2014-06-05 16:53:01 JordanBelfort
new thing :)
2014-06-03 12:19:01 Sumanth Bandi
good one :)
now I can do nCr any time without worrying about TLE
2014-03-26 18:51:40 Master_Mind
MY PROGRAM is not working ih ave tried all possible approches.
although it works fine on ideone and codeblocks

https://ideone.com/U1sDaX
my ideone link

@Adrian Kuegel plzz check
2014-02-15 06:19:14 RAJAT SINGH
essy one bt should be knowledge of pnc and also should be knowledge to calculate the factorial for large no.
2014-01-02 15:48:39 ABHISHEK004
easy prob...
if u are good in PnC u can do it very well :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.