RP - Life, the Universe, and Everything II

This problem tests your mathematic knowledge and your programming ability very much. Your task is to calculate the number of different Minimum Spanning Trees (MSTs) of a special undirected unweighted graph. The graph has n nodes numbered from 1 to n, and there is an edge between node i (1 ≤ i ≤ n) and node j (1 ≤ j ≤ n) if and only if 0 < |i-j| ≤ k.

Input

Multiple test cases, the number of them (≤ 8) is given in the very first line.

Each test case contains one line with two space-separated numbers k (1 ≤ k ≤ 5) and n (1 ≤ n ≤ 1015).

Output

For each test case you should output one line, the number of different MSTs of the corresponding graph modulo 65521.

Example

Input:
1
3 5

Output:
75

Added by:Fudan University Problem Setters
Date:2007-08-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:Chinese National Olympiad in Informatics 2007,Day 2; Translated by Blue Mary

hide comments
2009-05-20 13:10:23 Benjamin Jones
@Paul Draper
Yes! Just count unique spawn trees.
A spawn tree is unique iif its prufer code is unique.
(hey i'm hinting you)
2009-04-28 10:17:00 Paul Draper
What trees are unique? Is 1-2-3 unique from 2-1-3?
2009-04-28 10:09:21 Paul Draper
How does a minimum spanning tree and a general tree differ in an unweighted graph?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.