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.awt.geom.*;
import java.io.*;
import java.util.*;
import java.util.stream.*;

public class Edu87D {
    private static boolean debug = false;

    private static int N;

    private static void solveProblem(InputStream instr) throws Exception {
        InputReader sc = new InputReader(instr);
        int testCount = sc.nextInt();
       /* if (debug) {
            testCount = sc.nextInt();
        }*/

        for (int t = 1; t <= testCount; t++) {
            printDebug("------ " + t + " ------");
            N = 2 * sc.nextInt();
          //  A = readInts(sc, N);
            Object result = solveTestCase();
            System.out.println(result);
        }
    }

    private static Object solveTestCase() {
        Path2D.Double path = new Path2D.Double();
        path.moveTo(0, 0);
        double angle = 2 * Math.PI / N;
        double x1 = 0, y1 = 0;
        for(int i = 0; i < N; i++){
            double currAngle = -1 * angle * (i + 1);
            double x2 = x1 + Math.cos(currAngle);
            double y2 = y1 + Math.sin(currAngle);
            path.lineTo(x2, y2);
         //   System.out.println(x2 + "  " + y2);
            x1 = x2;
            y1 = y2;
        }
        path.closePath();
        Rectangle2D rect = path.getBounds2D();
     //   System.out.println(rect);
        double min = Math.max(Math.abs(rect.getWidth()), Math.abs(rect.getHeight()));
        double minAngle = 0;
        double maxAngle = angle;
        while(maxAngle - minAngle > 0.0000001) {
            double currAngle = minAngle + (maxAngle - minAngle) / 2;
            path = getTransformedInstance(path, currAngle);
            rect = path.getBounds2D();
            double currVal = Math.max(Math.abs(rect.getWidth()), Math.abs(rect.getHeight()));
            if (currVal < min) {
                minAngle = currAngle;
                min = currVal;
            } else {
                maxAngle = currAngle;
            }
        }
        return min;
    }

    private static Path2D.Double getTransformedInstance(Path2D path, double angle) {
        AffineTransform at = new AffineTransform();
        Rectangle2D bounds = path.getBounds();
        //at.rotate(angle, bounds.getX() + (bounds.getWidth() / 2), bounds.getY() + (bounds.getHeight() / 2));
        at.rotate(angle, 0, 0);
        at.translate(0, 0);
        return (Path2D.Double) path.createTransformedShape(at);
    }

    private static int[] readInts(InputReader sc, int N) throws Exception {
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        return arr;
    }

    private static String joinValues(List<? extends Object> list, String delim) {
        return list.stream().map(Object::toString).collect(Collectors.joining(delim));
    }

    private static String joinValues(int[] arr, String delim) {
        List<Object> list = new ArrayList<>();
        for (Object value : arr) {
            list.add(value);
        }
        return list.stream().map(Object::toString).collect(Collectors.joining(delim));
    }

    public static void printDebug(Object str) {
        if (debug) {
            System.out.println("DEBUG: " + str);
        }
    }


    private static void printOut(String out) {
        System.out.println(out);
    }

    public static String printArr(int[] arr) {
        StringBuilder builder = new StringBuilder();
        for (int in : arr) {
            builder.append(in).append(" ");
        }
        return builder.toString();
    }

    private static final class InputReader {
        private final InputStream stream;
        private final byte[] buf = new byte[1024];
        private int curChar;
        private int Chars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        private int read() throws Exception {
            if (curChar >= Chars) {
                curChar = 0;
                Chars = stream.read(buf);
                if (Chars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public final int nextInt() throws Exception {
            return (int)nextLong();
        }

        public final long nextLong() throws Exception {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
                if (c == -1)
                    throw new IOException();
            }
            boolean negative = false;
            if (c == '-') {
                negative = true;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += (c - '0');
                c = read();
            } while (!isSpaceChar(c));
            return negative ? (-res) : (res);
        }

        public final int[] nextIntBrray(int size) throws Exception {
            int[] arr = new int[size];
            for (int i = 0; i < size; i++)
                arr[i] = nextInt();
            return arr;
        }

        public final String next() throws Exception {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.append((char)c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public final String nextLine() throws Exception {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.append((char)c);
                c = read();
            } while (c != '\n' && c != -1);
            return res.toString();
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    }

    public static void main(String[] args) throws Exception {
        long currTime = System.currentTimeMillis();
        try {
            if (new File("input.in").exists()) {
                debug = true;
            }
        } catch (Throwable ex) {

        }
        if (debug) {
            solveProblem(new FileInputStream(new File("input.in")));
            System.out.println("Time: " + (System.currentTimeMillis() - currTime));
        } else {
            solveProblem(System.in);
        }
    }

}