Problem: The statement of this problem is the same as the statement of problem C2. 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 even integer n (2 ≤ n ≤ 200). 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
2
4
200


Output


1.000000000
2.414213562
127.321336469

Solution (in JAVA):

Solution:


import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    private static final double A = 1;

    static class Pos{

        public Pos(Pos pos){
            this.x = pos.x;
            this.y = pos.y;
        }
        public Pos(){

        }
        public double x;
        public double y;
    }

    public static List<Pos> generateRectangleList(Integer countPoint){

        List<Pos> rectanglePoints = new ArrayList<Pos>();

        double curAng = 0;
        double stepAng = 360.0 / (double)countPoint;
        double calcAnge= 180.0 / (double)countPoint;
        double R = A / (2.0 * Math.sin(Math.toRadians(calcAnge)));

        for (int i=0;i<countPoint;i++){
            Pos pos = new Pos();
            pos.x = R*Math.cos(Math.toRadians(curAng));
            pos.y = R*Math.sin(Math.toRadians(curAng));
            curAng+=stepAng;
            rectanglePoints.add(pos);
        }

        return rectanglePoints;
    }



    public static void rotatePolygons(List<Pos> points, double angle){
        for ( Pos pos : points){
            Pos oldPos = new Pos(pos);
            pos.x = oldPos.x*Math.cos(angle) - oldPos.y*Math.sin(angle);
            pos.y = oldPos.x*Math.sin(angle) + oldPos.y*Math.cos(angle);
        }
    }

    public static Double calcCurSize(List<Pos> points){

        List<Pos> twoPosX = new ArrayList<Pos>();
        List<Pos> twoPosY = new ArrayList<Pos>();

        for (int i=0;i<points.size()-1;i++){
            if ((points.get(i).y >= 0 && points.get(i+1).y <= 0 ) || (points.get(i).y <= 0 && points.get(i+1).y >= 0 )){
                twoPosX.add(points.get(i));
                twoPosX.add(points.get(i+1));
            }
            if ((points.get(i).x >= 0 && points.get(i+1).x <= 0 ) || (points.get(i).x <= 0 && points.get(i+1).x >= 0 )){
                twoPosY.add(points.get(i));
                twoPosY.add(points.get(i+1));
            }

        }

        int i =points.size()- 1;

        if ((points.get(i).y >= 0 && points.get(0).y <= 0 ) || (points.get(i).y <= 0 && points.get(0).y >= 0 )){
            twoPosX.add(points.get(i));
            twoPosX.add(points.get(0));
        }
        if ((points.get(i).x >= 0 && points.get(0).x <= 0 ) || (points.get(i).x <= 0 && points.get(0).x >= 0 )){
            twoPosY.add(points.get(i));
            twoPosY.add(points.get(0));
        }

        Double X1;
        Double X2;

        if (twoPosX.get(0).x < twoPosX.get(2).x){
            X1 = Math.min(twoPosX.get(0).x,twoPosX.get(1).x);
            X2 = Math.max(twoPosX.get(2).x,twoPosX.get(3).x);
        }else{
            X1 = Math.max(twoPosX.get(0).x,twoPosX.get(1).x);
            X2 = Math.min(twoPosX.get(2).x,twoPosX.get(3).x);
        }

        Double Y1;
        Double Y2;

        if (twoPosY.get(0).y < twoPosY.get(2).y){
            Y1 = Math.min(twoPosY.get(0).y,twoPosY.get(1).y);
            Y2 = Math.max(twoPosY.get(2).y,twoPosY.get(3).y);
        }else{
            Y1 = Math.max(twoPosY.get(0).y,twoPosY.get(1).y);
            Y2 = Math.min(twoPosY.get(2).y,twoPosY.get(3).y);
        }


        return Math.max(Math.abs(X1-X2),Math.abs(Y1-Y2));
    }





    public static Double calcMinPossibleSize(Integer countAngle){
        List<Pos> polygon = generateRectangleList(countAngle);
        Double targetAngle = Math.toRadians(new Double(360.0 / (double)countAngle));
        Double rotAngle = targetAngle / 100.0;
        Double currentAngle = 0.0;

        Double MIN = 999999999.0;

        while (currentAngle < targetAngle){
            Double curSize = calcCurSize(polygon);
            if (curSize < MIN) MIN = curSize;
            rotatePolygons(polygon,rotAngle);
            currentAngle+=rotAngle;
        }

        return MIN;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
	    Integer T = scanner.nextInt();
	    for (int i = 0;i<T;i++){
            Integer n = scanner.nextInt();
            System.out.println(calcMinPossibleSize(2*n));
        }
    }
}