Help King

题意翻译

### 题目背景 很久很久以前，一个遥远国度的公主$\mathtt{Victoria}$ 快乐地过着王室生活，但是有一天就不快乐了：恶龙袭击了王国，带走了可爱的 $\mathtt{Victoria}$。国王悲痛欲绝，他迅速喊来皇家骑士，有谁能从这个地狱猛手中救回 $\mathtt{Victoria}$，就把王国一半的土地和赏赐给他，并让公主嫁给这位勇士。 冒险途中，骑士们发现了恶龙的巢穴，奋不顾身地冲过去救 $\mathtt{Victoria}$。每个骑士都向罪大恶极的龙啐了一口（什么离谱攻击方式），可怜的龙因脆弱的心碎了而倒地。那些骑士将 $\mathtt{Victoria}$ 送到国王那儿，然后就不要脸地吵起来了，他们都想娶可爱的 $\mathtt{Victoria}$。 问题是所有骑士都一模一样，很高贵，很英俊，$\mathtt{Victoria}$ 却不想嫁给任何一个骑士。然后聪明的国王不想伤了任何人的感情，决定用抛硬币的方式随机挑一个骑士。 ### 题目描述 国王决定用抛硬币的方式随机挑一个骑士。坏消息是，有 $n$ 个骑士，硬币却只有两面。好消息是，抛完硬币，每一面朝上的概率是相等的。国王很好奇如何用硬币以相等的概率选出一位骑士(此概率应该始终等于 $\dfrac1n$)。 首先，国王想知道他需要抛多少次硬币来选出赢家。此外，在抛硬币时，国王应该遵循最佳抛硬币策略(即使抛硬币的期望次数最小的策略)。请你帮助国王完成这个具有挑战性的任务。 ### 输入格式 第一行一个整数 $n\space(1\le n\le 10000)$，如题中描述。 ### 输出格式 以不可约的分数 “$a/b$”（忽略引号）的形式输出抛掷的期望次数，去掉前导零。

题目描述

This is the modification of the problem used during the official round. Unfortunately, author's solution of the original problem appeared wrong, so the problem was changed specially for the archive. Once upon a time in a far away kingdom lived the King. The King had a beautiful daughter, Victoria. They lived happily, but not happily ever after: one day a vicious dragon attacked the kingdom and stole Victoria. The King was full of grief, yet he gathered his noble knights and promised half of his kingdom and Victoria's hand in marriage to the one who will save the girl from the infernal beast. Having travelled for some time, the knights found the dragon's lair and all of them rushed there to save Victoria. Each knight spat on the dragon once and, as the dragon had quite a fragile and frail heart, his heart broke and poor beast died. As for the noble knights, they got Victoria right to the King and started brawling as each one wanted the girl's hand in marriage. The problem was that all the noble knights were equally noble and equally handsome, and Victoria didn't want to marry any of them anyway. Then the King (and he was a very wise man and didn't want to hurt anybody's feelings) decided to find out who will get his daughter randomly, i.e. tossing a coin. However, there turned out to be $ n $ noble knights and the coin only has two sides. The good thing is that when a coin is tossed, the coin falls on each side with equal probability. The King got interested how to pick one noble knight using this coin so that all knights had equal probability of being chosen (the probability in that case should always be equal to $ 1/n $ ). First the King wants to know the expected number of times he will need to toss a coin to determine the winner. Besides, while tossing the coin, the King should follow the optimal tossing strategy (i.e. the strategy that minimizes the expected number of tosses). Help the King in this challenging task.

输入输出格式

输入格式

The first line contains a single integer $ n $ from the problem's statement ( $ 1<=n<=10000 $ ).

输出格式

Print the sought expected number of tosses as an irreducible fraction in the following form: " $ a $ / $ b $ " (without the quotes) without leading zeroes.

输入输出样例

输入样例 #1

2

输出样例 #1

1/1

输入样例 #2

3

输出样例 #2

8/3

输入样例 #3

4

输出样例 #3

2/1