问题 F: PSO

Particle swarm optimization ( PSO ) is a population-based stochastic optimization algorithm. In addition to the basic structure of PSO, there is also a variant called star-topology PSO, which introduces a star-shaped communication structure among particles. In this structure, there is a central particle called the leader, which is responsible for gathering and disseminating information to the rest of the particles in the swarm.

Now there are $n$ particles on the star-topology. Among the $n$ particles, there is one particle as the leader, and there is an edge between the other particles and the leader. For a piece of information, it can be propagated along an edge on the topology.

To examine the benefits of this topology, we need to calculate the following data:

We define that $X$ is number of edges required for them to exchange information for two different particles. Please calculate the expected value and maximum value of $X$.

The first line of input is a positive integer $T(T\le 10^5)$ representing the number of test cases.

For each line,input a number $n(2\le n\le 10^9)$.