45. NTHU Coding Throne 2016 - E. Farey Sequences

0 Judge

Code: 0


Farey Sequences

題目敘述

Farey sequences are named after the British geologist John Farey. The Farey sequence of order $N$ consists all the fractions $a/b$ that satisfy the following conditions:

  • $0 \leq a \leq b$

  • $1 \leq b \leq N$

  • The greatest common divisor of $a$ and $b$ equals $1$.

  • The sequence is monotonically increasing.

For example, the Farey sequence of order 5 is: $0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1.$

By letting the denominators of the Farey sequence of order $N$ be $d[1]$, $d[2]$, $\cdots$, $d[k]$, the Farey sum of order $N$ is the sum of $d[i]/d[i+1]$ for all $1 \leq i \leq k-1$.

For example, the Farey sum of order 5 is $1/5+5/4+4/3+3/5+5/2+2/5+5/3+3/4+4/5+5/1=29/2$.

Now given integer $N$, it is your task to compute the Farey sum of order $N$.

輸入說明

The first line of the input contains an integer $T$ ($1 \leq T \leq 10000$), the number of test cases. There is only one line of input per test case containing a single integer $N$ ($1 \leq N \leq 10^{6}$), of which the Farey sum of the order $N$ is to be computed.

輸出說明

For each test case, there is a single line of output consisting the Farey sum as a decimal fraction in lowest terms. If the denominator is 1, only the numerator should be printed.

範例輸入

2
2
5

範例輸出

5/2
29/2

提示

no


Judge Setting

run-time limit: 1500 ms
memory limit: 2621440 byte
測資數量: 0