Problem: The statement of this problem is the same as the statement of problem C1. The only difference is that, in problem C1, n is always even, and in C2, n is always odd.

You are given a regular polygon with 2 ⋅ n vertices (it's convex and has equal sides and equal angles) and all its sides have length 1. Let's name it as 2n-gon.

Your task is to find the square of the minimum size such that you can embed 2n-gon in the square. Embedding 2n-gon in the square means that you need to place 2n-gon in the square in such way that each point which lies inside or on a border of 2n-gon should also lie inside or on a border of the square.

You can rotate 2n-gon and/or the square.

Input

The first line contains a single integer T (1 ≤ T ≤ 200) — the number of test cases.

Next T lines contain descriptions of test cases — one per line. Each line contains single odd integer n (3 ≤ n ≤ 199). Don't forget you need to embed 2n-gon, not an n-gon.

Output

Print T real numbers — one per test case. For each test case, print the minimum length of a side of the square 2n-gon can be embedded in. Your answer will be considered correct if its absolute or relative error doesn't exceed 10^{-6}.

Example

Input


3
3
5
199


Output


1.931851653
3.196226611
126.687663595

Solution (in JAVA):

Solution:
import java.io.*;
import java.math.*;
import java.util.*;

public class n3{
//	static PrintWriter out=new PrintWriter(System.out);
	public static double solve(int n){
		n*=2;
		double minx=1000000;
		double maxx=-1000000;
		double miny=1000000;
		double maxy=-1000000;
		Complex init=new Complex(0,Math.sqrt(2)/2);
		Complex dir=new Complex(Math.cos(Math.PI/4),-Math.sin(Math.PI/4));
		Complex rot=new Complex(Math.cos(2*Math.PI/n),Math.sin(2*Math.PI/n));
		for(int i=0;i<2*n;i++) {
			init=init.plus(dir);
			dir=dir.times(rot);
			double x=init.re();
			double y=init.im();
			minx=Math.min(minx,x);
			maxx=Math.max(maxx,x);
			miny=Math.min(miny,y);
			maxy=Math.max(maxy,y);
//			System.out.println(init);
		}
		return Math.max(maxx-minx,maxy-miny);
	}
	public static void main(String[] args) throws Exception{
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));//(System.in));
		int t=Integer.parseInt(in.readLine());
		for(int tt=0;tt<t;tt++){
			System.out.println(solve(Integer.parseInt(in.readLine())));
		}
	}
}
class Complex{
	private final double re;   // the real part
	private final double im;   // the imaginary part

	// create a new object with the given real and imaginary parts
	public Complex(double real,double imag){
		re=real;
		im=imag;
	}

	// return a string representation of the invoking Complex object
	public String toString(){
		if(im==0)
			return re+"";
		if(re==0)
			return im+"i";
		if(im<0)
			return re+" - "+(-im)+"i";
		return re+" + "+im+"i";
	}

	// return abs/modulus/magnitude
	public double abs(){
		return Math.hypot(re,im);
	}

	// return angle/phase/argument, normalized to be between -pi and pi
	public double phase(){
		return Math.atan2(im,re);
	}

	// return a new Complex object whose value is (this + b)
	public Complex plus(Complex b){
		Complex a=this;             // invoking object
		double real=a.re+b.re;
		double imag=a.im+b.im;
		return new Complex(real,imag);
	}

	// return a new Complex object whose value is (this - b)
	public Complex minus(Complex b){
		Complex a=this;
		double real=a.re-b.re;
		double imag=a.im-b.im;
		return new Complex(real,imag);
	}

	// return a new Complex object whose value is (this * b)
	public Complex times(Complex b){
		Complex a=this;
		double real=a.re*b.re-a.im*b.im;
		double imag=a.re*b.im+a.im*b.re;
		return new Complex(real,imag);
	}

	// return a new object whose value is (this * alpha)
	public Complex scale(double alpha){
		return new Complex(alpha*re,alpha*im);
	}

	// return a new Complex object whose value is the conjugate of this
	public Complex conjugate(){
		return new Complex(re,-im);
	}

	// return a new Complex object whose value is the reciprocal of this
	public Complex reciprocal(){
		double scale=re*re+im*im;
		return new Complex(re/scale,-im/scale);
	}

	// return the real or imaginary part
	public double re(){
		return re;
	}
	public double im(){
		return im;
	}

	// return a / b
	public Complex divides(Complex b){
		Complex a=this;
		return a.times(b.reciprocal());
	}

	// return a new Complex object whose value is the complex exponential of this
	public Complex exp(){
		return new Complex(Math.exp(re)*Math.cos(im),Math.exp(re)*Math.sin(im));
	}

	// return a new Complex object whose value is the complex sine of this
	public Complex sin(){
		return new Complex(Math.sin(re)*Math.cosh(im),Math.cos(re)*Math.sinh(im));
	}

	// return a new Complex object whose value is the complex cosine of this
	public Complex cos(){
		return new Complex(Math.cos(re)*Math.cosh(im),-Math.sin(re)*Math.sinh(im));
	}

	// return a new Complex object whose value is the complex tangent of this
	public Complex tan(){
		return sin().divides(cos());
	}

	// a static version of plus
	public static Complex plus(Complex a,Complex b){
		double real=a.re+b.re;
		double imag=a.im+b.im;
		Complex sum=new Complex(real,imag);
		return sum;
	}

	// See Section 3.3.
	public boolean equals(Object x){
		if(x==null)
			return false;
		if(this.getClass()!=x.getClass())
			return false;
		Complex that=(Complex)x;
		return (this.re==that.re)&&(this.im==that.im);
	}

	// See Section 3.3.
	public int hashCode(){
		return Objects.hash(re,im);
	}
}