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:1s
Source limit:10000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: NODEJS PERL 6
Resource:own problem

hide comments
2014-03-26 18:51:40 SHIVAM DUGGAL
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 :)
2014-01-02 10:30:12 topgun
the segmentation fault continues to trouble ... any hints ... ??
2013-12-29 19:33:21 mayank
The trick here is that the input are such that the answer can never exceed 10^18 period.
2013-12-24 04:51:05 Altamir Gomes Bispo Junior [UFSCar]
An interesting challenge for all: try to solve this problem w/o resorting to BigInt.
2013-12-24 03:25:27 Altamir Gomes Bispo Junior [UFSCar]
@ Ravi, you may need to do a little more thinking in order to avoid the segfault... it's a piece of the problem ;-)
2013-12-24 02:00:12 Martijn Muijsers
Really cool problem!
2013-09-10 16:04:07 Ravi Vishwakarma
http://ideone.com/K2lYgq

my code works fine for the given test case but gives a segmentation fault on submission. Please can someone point out the mistake
2013-07-19 17:45:53 jagadeesh babu chitta
im nt gettin how 30c7 results 475020..!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.