AE2A  Dice
Jack claims that he has telekinetic powers. He has made a bet with Mike that he would throw a die n times and would get exactly k pips in total. Jack's die has 6 faces with numbers from 1 to 6 written on them and is perfectly symmetric. Mike does not believe in Jack's telekinetic powers (in general, being a tenacious rationalist, he does not believe in telekinesis), but he is concerned that Jack could win the bet simply by luck. Therefore, he would like to know what is the chance (in percent) of such an unlucky event, and asked you to write a program that would help him solve this problem.
Input
The first line of the standard input contains a single integer t (1 ≤ t ≤ 20) denoting the number of test cases. Each of the following t lines contains a description of one test case in the form of two integers n_{i} and k_{i} (1 ≤ n_{i}, k_{i} ≤ 10^{6}) separated by a single space.
Output
To the standard output t lines should be written, containing the answers to respective test cases. The answer to one test case is the probability (in percent) that Jack wins the bet, rounded down to the nearest integer.
Example
For the input data:
1 1 6
the correct result is:
16
Task author: Jakub Onufry Wojtaszczyk.
hide comments
ssunitk:
20170509 21:41:11
Last edit: 20170509 21:44:43 

holmesherlock:
20170122 23:53:08
ya plz explain how you got those bounds..@Shubham Matta 

Amrit Raj:
20160929 16:53:33
I don't know whats going wrong with the code, it's giving WA if anyone can help


abobakr_pp:
20160830 12:37:55
@Shubham Matta How did you know these bounds ?? 

theph0enix:
20160608 17:11:51
Nice question. There are bounds where you can simply output 0. Hint: central limit theorem => normal distribution! ;) Last edit: 20160609 00:25:19 

Saurabh Kr Singh:
20160402 20:48:19
@yashmittal I got acc with solution giving 4 for (3,6) 

Shubham Matta:
20160401 01:09:20
SO main problem is the bounds ... they are till 545 (n) and 1908 (k) .. after that the answer is 0 for all n,k. 

yashmittal:
20160302 09:44:55
can anyone explain how (3,6) will give 0 probablity percent of getting 6 when dice is rolled 3 times


sarvesh_19:
20160219 22:55:31
bottom up recursion giving tle iterative top down accepted. please help :( http://ideone.com/9aAgcv.


r_ash:
20160120 08:33:00
the total number of favorable cases is larger than the range of unsigned long long int...what can I do now?

Added by:  Race with time 
Date:  20090503 
Time limit:  0.150s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Algorithmic Engagements 2009 