Description

In the near future, with the deterioration of the earth's natural environment, human beings are facing the threat of being unable to survive. But there's still hoping: scientists found a wormhole near saturn in our solar system which connects a piece of space near a blackhole that a habitable planet is moving around it. Dr.cooper is considering to send his daughter, Murphy, to explore the specific environment of that planet. But the timespace around the blackhole is twisted severely, so Murphy must get started researching this strange timespace.

She found that every single person can avoid the influence from the twisted timespace by spliting the space with some hyperplanes into many parts. Then each person can hide into a part and he will not get influented.

The hyperplane means that, for example, in 3-dimensional space, whose hyperplane is a 2-dimensional space that is a plane; and in 2-dimensional space, whose hyperplane is 1-dimensional space that is a line. So a n-dimensional space whose hyperplane is (n-1)-dimensional space.

So Murphy want you to help her find out the result of how many different parts a n-dimensional space can be splited mostly by m hyperplanes.

Format

Input

The first line of input is an integer $T(1 \leq T \leq 100000)$ represents the number of cases. Then there will be T lines following, each line is a case of two integer $n(1 \leq n \leq 5)$ and $m(0 \leq m \leq 16000)$ represent a n-dimensional space and $m$ hyperplanes.

Output

There will be $T$ lines output and the ith line is the result of the ith case.

Samples

3
2 3
3 2
1 4

7
4
5

Hints