Dice

Time limit1sMemory limit128 MB

Summary

Given n and k, find the number of ways n fair dice can sum to k, then output the integer part of 100 times that probability.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Math, Probability
Solved: No attempts yet

Problem

Jack claims that he has telekinetic powers. He has bet Mike that he can throw a die $n$ times and make the pips add up to exactly $k$ . Jack's die is a perfectly symmetric cube with the numbers $1$ through $6$ on its faces. Mike does not believe in telekinesis, but he is worried that Jack might win the bet by pure luck. He therefore wants to know the chance (as a percentage) of such an unlucky event, and asks you to write a program that computes it.

In other words, throw a fair die $n$ times and find, as a percentage, the probability that the pips add up to exactly $k$ .

Input

The first line contains a single integer $t$ ( $1 \le t \le 20$ ), the number of test cases. Each of the next $t$ lines contains two integers $n$ and $k$ ( $1 \le n, k \le 10^6$ ) separated by a single space, where $n$ is the number of throws and $k$ is the target sum of pips.

Output

For each test case, print on its own line the probability (as a percentage) that Jack wins the bet, rounded down to the nearest integer. That is, print the integer part of $100$ times the probability that $n$ throws of a fair die sum to exactly $k$ .

Examples4

Example 1
Input
```
1
1 6
```
Expected output
```
16
```

Example 2

Input

Expected output

Example 3
Input
```
5
2 2
2 3
2 7
2 11
2 12
```
Expected output
```
2
5
16
5
2
```
Example 4
Input
```
4
3 2
2 13
1 7
5 4
```
Expected output
```
0
0
0
0
```