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