Under construction

Still being built. Things may change

Filling Diamonds

Time limit1sMemory limit1024 MB

Summary
Count the ways to cover a belt-shaped region of 4n-2 triangles with diamonds, for up to 10^4 queries with n up to 10^9.
Level

Medium5 of 10

Topics
Combinatorics, Math
Solved
No attempts yet

Problem

You are given an integer nn. Count the ways to completely cover a belt-like region of 4n−24n-2 triangles with diamond shapes.

A diamond is made of two triangles. You may move, rotate, or flip a diamond, but you may not scale it. Two coverings are different if there are two triangles that are covered by the same diamond in one covering but by different diamonds in the other.

See the pictures below. The diamond on the left is the shape you will use, and the region on the right is the one you need to fill.

The figures show the region for n=1,2,3,4n = 1, 2, 3, 4.

Answer tt independent test cases.

Input

The first line contains a single integer tt (1≤t≤1041 \le t \le 10^{4}), the number of test cases.

Each of the next tt lines contains a single integer nn (1≤n≤1091 \le n \le 10^{9}).

Output

For each test case, print the number of ways to fully cover the belt-like region of 4n−24n-2 triangles with diamond shapes. Under the given constraints, this number does not exceed 101810^{18}.

Hint

In the first test case, there are 2 ways to fill the region.

In the second test case, there is only one way to fill the region.

Examples1

  1. Example 1

    Input
    2
    2
    1
    
    Expected output
    2
    1