HANOI07 - Building the Tower

no tags 

There are N cubes in a toy box which has 1-unit height, the width is double the height. The teacher organizes a tower-building game. The tower is built by the cubes. The height of the tower is H (h levels). The bottom of the tower contains M cubes; and for all above level, each must contains a number of cubes which is exactly 1 less than or greater than the number of cubes of the level right below it. Your task is to determine how many different towers can be there. Two towers are considered different if there is at least one number i (1< i <=H) so that the i'th level of one tower contains a different number of cubes to the i'th level of the other tower.

Input

The first line of input file is the integer number t ( 0 < t < 1002 ) , the number of test cases . Each test case in one line , the line contains three positive number N, H and M (N <= 32767, H<=60, M<=10).

Output

With each test case , write in one line , the total of different towers that can be founded.

Example

Input:
2
7 3 2
22 5 4
Output:
2
10
(* In the first test case , all the towers are : 2-1-2 , 2-3-2 . *)

hide comments
hodobox: 2019-11-26 15:41:49

the toy box height/width has nothing to do with solving the problem

林星宇: 2012-06-26 08:28:35

CAN 2200*H*H*M PASS THIS PROBLEM?
GETTING TLE ALL THE TIME

つ ◕_◕ ༽つ GIFF AC: 2011-10-19 16:32:05

do the toy box height/width have anything to do with solving the problem?

Last edit: 2011-10-19 16:32:30
darryl: 2011-09-20 02:54:38

Really Nice Problem! :D

Chandan Giri: 2011-09-17 19:31:51

nice problem :)

Tony Beta Lambda: 2009-09-29 04:57:18

64-bit integers are necessary.

[Trichromatic] XilinX: 2009-03-18 02:35:53

:) Read the problem statement CAREFULLY.


Added by:Nguyen Minh Hieu
Date:2005-12-30
Time limit:1s
Source limit:7777B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:ACM