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

Solution:
import math


def ternary_search(left, right, n, exterior_angle):
    while True:
        left_val = calculate_side_length(left, n, exterior_angle)
        right_val = calculate_side_length(right, n, exterior_angle)
        if abs(left_val - right_val) < 1e-7 and abs(left-right) < 1e-7:
            return left_val

        left_third = left + (right - left) / 3
        right_third = right - (right - left) / 3

        if calculate_side_length(left_third, n, exterior_angle) > calculate_side_length(right_third, n, exterior_angle):
            left = left_third
        else:
            right = right_third


def calculate_side_length(alpha, n, exterior_angle):
    rad_alpha = alpha * math.pi / 180
    width = math.cos(rad_alpha)
    height = math.sin(rad_alpha)
    for i in range(n // 2):
        angle = (i + 1) * exterior_angle
        left_angle = angle - rad_alpha
        right_angle = angle + rad_alpha
        if right_angle > math.pi / 2:
            right_angle -= math.pi / 2
        width += math.cos(left_angle) + math.cos(right_angle)
        height += math.sin(left_angle) + math.sin(right_angle)
    side_length = max(width, height)
    # print(f'alpha:{alpha}, width:{width:.2f}, height:{height:.2f}'
    #       f' right_angle:{right_angle*180/math.pi:.2f}, left_angle:{left_angle*180/math.pi:.2f}')
    return side_length


def main(n):
    exterior_angle = math.pi / n
    # for alpha in range(90//n):
    #     calculate_side_length(alpha, n, exterior_angle)
    ans = ternary_search(0, 90//n + 1, n, exterior_angle)
    print(ans)


if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        n = int(input())
        main(n)
    # main(3)