CZ_PROB4 - Dividing Spaces

no tags 

Into how many parts can k cuts using an n-1 dimensional hyper-plane divide an n- dimensional hypercube?

Hint: Experiment with n=2, n=3 find a pattern
Eg: n=3, k=5 => dividing a cube with 5 cuts using planes.

Input

T, number of test cases followed by T lines of 'n' and 'k'.

Output

The number of parts in separate lines for each of 'T' test cases.

Example

Input:
2
14 20
6 23

Output:
1026876
145499



Added by:Rahul
Date:2007-03-11
Time limit:3.283s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Dilip Rajeev