CHEFFEB - Bogosort

no tags 

Recently Johnny have learned bogosort sorting algorithm. He thought that it is too ineffective. So he decided to improve it. As you may know this algorithm shuffles the sequence randomly until it is sorted. Johnny decided that we don't need to shuffle the whole sequence every time. If after the last shuffle several first elements end up in the right places we will fix them and don't shuffle those elements furthermore. We will do the same for the last elements if they are in the right places. For example, if the initial sequence is (3, 5, 1, 6, 4, 2) and after one shuffle Johnny gets (1, 2, 5, 4, 3, 6) he will fix 1, 2 and 6 and proceed with sorting (5, 4, 3) using the same algorithm. Johnny hopes that this optimization will significantly improve the algorithm. Help him calculate the expected amount of shuffles for the improved algorithm to sort the sequence of the first n natural numbers given that no elements are in the right places initially.

Input

The first line of input file is number t - the number of test cases. Each of the following t lines hold single number n - the number of elements in the sequence.

Constraints

1 <= t <= 175
2 <= n <= 175

Output

For each test case output the expected amount of shuffles needed for the improved algorithm to sort the sequence of first n natural numbers in the form of irreducible fractions.

Example

Input:
3
2
6
10

Output:
2
1826/189
877318/35343

hide comments
Paul Draper: 2014-10-09 22:34:18

FYI, this isn't really a sort. If you know if elements are in the eventual right places, you must've already sorted them.

Akhil Gupta: 2014-06-25 08:47:35

On the leaderboard. 1st :D

Ravi Kiran: 2013-12-27 10:42:40

Optimized my codechef solution (which were O(N*N) during precompute), to be O(N) overall.
Passed with a great time! :-)

Spooky: 2011-03-27 11:16:01

Constraints are a bit higher here.
TL is two times my Java AC solution.

abhijith reddy d: 2011-03-27 10:58:10

Same here.

Radhakrishnan Venkataramani: 2011-03-27 10:29:57

AC solution in codechef gets TLE here ...
You have to allow Java solutions to pass


Added by:Spooky
Date:2011-03-27
Time limit:1s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CodeChef February Challenge 2011