This problem is a programming version of Problem 213 from projecteuler.net
An grid of squares contains fleas, initially one flea per square.
When a bell is rung, each flea jumps to an adjacent square at random (usually possibilities, except for fleas on the edge of the grid or at the corners).
What is the expected number of unoccupied squares after rings of the bell? As this number is rational, it could be represented as . Give your answer as . It's guaranteed that is coprime to .
Input Format
The first line of each test file contains a single integer , which is the number of queries per test file. lines follow with integers and on each, separated by a single space.
Constraints
- is even
- Sum of all in each test file
Output Format
Print exactly lines with an answer for the corresponding query on each.
Sample Input 0
1
2 1
Sample Output 0
1
Explanation 0
At the beginning, the field looks as follows:
After the only bell ring there could be variants:
So we have variants with free cells, variants with free cell and variants with free cells. That means, the expected number of empty cells is equal to .