Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Push Botton Lock
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1544Accepted: 978

Description

The Frobozz Magic Lock Company is in the business of manufacturing push button style combination door locks. A push button door lock consists of a number of push buttons B, (1 ≤ B ≤ 11), labeled “1” through “B”. The lock is opened by pressing the correct sequence of button combinations and then turning the doorknob. If the sequence of presses is correct, the door magically opens.

A combination consists of 1 or more buttons being pressed simultaneously. A sequence consists of a series of combinations. A sequence must have at least one combination. Once a button has been used in a combination, it may not be used again in the same sequence. In addition, it is not necessary to use all the buttons in a sequence. For example, for B = 8:

(1-2-3)(4)(7-8)

is a valid sequence with 3 combinations (1-2-3), (4), and (7-8). Note that buttons 5 and 6 are not used in this sequence.

(1-2-3)(2-4)(5-6)

is not a valid sequence, since button 2 appears in 2 combinations (1-2-3) and (2-4).

The CEO of Frobozz, J. Pierpont Flathead, wants you to write a program that determines the number of valid sequences possible for given values of B. The program must be able to process a list of lock orders (datasets) from customers and generate a report showing the order number, the value of B, and the number of valid sequences possible. This list will always contain at least one dataset, but no more than 100 datasets.

Reference Materials:


J. Pierpont Flathead

Input

The first line of input contains a single integer N, (1 ≤ N ≤ 100), representing the number of datasets that follow. Each dataset consists of a single line of data containing a single integer B, which is the number of buttons for the lock.

Output

For each dataset, display the dataset number, a blank, the value B, a blank, and the number of valid sequences.

Sample Input

3
3
4
3

Sample Output

1 3 25
2 4 149
3 3 25

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator