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
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?


DHEERAJ KUMAR:
20160116 22:17:10
extremely fucking problem. same code after 30 submissions showed AC. Dont race with time while setting problems. 

Piyush Kumar:
20151211 08:51:26
@shyam , There are no trick test cases as such. I wrote a straightforward dp solution and it passed. 

Amit Ajaat:
20150630 16:00:20
YOU "Race with time" , atleast, explain the problems clearly, hiding something is not going to make you best coder or best problem setter.......what this pips represent, what "exactly k pips in total" means, you are the one who is


shyam:
20150619 07:54:56
wrong answer ...any trick test cases??


Brian Bi:
20090930 08:53:35
A pip is simply one of those marks on the face of a die. So "exactly k pips in total" should be interpreted as "a sum of k". 
Added by:  Race with time 
Date:  20090503 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Algorithmic Engagements 2009 