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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
struct point {
  double x, y;
} P[MAXN];
point rotate(point a, double r) {
  point ret;
  ret.x = a.x * cos(r) - a.y * sin(r);
  ret.y = a.x * sin(r) - a.y * cos(r);
  return ret;
}
double side_length(int n, double r) {
  double maxx, maxy, minx, miny;
  maxx = maxy = -INT_MAX;
  minx = miny = INT_MAX;
  for (int i = 0; i < n; ++i) {
    point p = rotate(P[i], r);
    double x = p.x, y = p.y;
    maxx = max(maxx, x);
    minx = min(minx, x);
    maxy = max(maxy, y);
    miny = min(miny, y);
  }
  return max(maxx - minx, maxy - miny);
}
void calc(int n) {
  double lo = 0.0, mid1, mid2, hi = acos(-1.0) / 2.0;
  while (lo + 1e-12 < hi) {
    mid1 = lo * 2.0 / 3.0 + hi * 1.0 / 3.0;
    mid2 = lo * 1.0 / 3.0 + hi * 2.0 / 3.0;
    if (side_length(n, mid1) > side_length(n, mid2))
      lo = mid1;
    else
      hi = mid2;
  }
  double side = side_length(n, lo);
  printf("%.8f\n", side);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    n *= 2;
    double angle = 180.0 - (double)(n * 180 - 360) / n;
    angle /= 2.0;
    double radius = 0.5 / sin(angle * acos(-1.0) / 180.0);
    angle *= 2.0;
    double tot = 0.0;
    for (int i = 0; i < n; ++i) {
      P[i].x = radius * sin(tot * acos(-1.0) / 180.0);
      P[i].y = radius * cos(tot * acos(-1.0) / 180.0);
      tot += angle;
    }
    calc(n);
  }
}