## PERIOD1 - Periodic function, trip 1

no tags xkcd/26

Let us consider periodic functions from Z to R.

```	def f(x): return [4, -6, 7][x%3] # (with Python notations)
# 4, -6, 7, 4, -6, 7, 4, -6, 7, 4, -6, 7, 4, -6, 7, ...
```

For example, f is a 3-periodic function, with f(0) = f(3) = f(6) = f(9) = 4.
With a simplified notation we will denote f as [4, -6, 7].

For two periodic functions (with integral period), here the quotient of periods will be rational, in that case it can be shown that the sum of the functions is also a periodic function.
Thus, the set of all such functions is a vector space over R.

Our interest, in this problem, will be the dimension of this space when the period is bounded by some integer N.

### Input

The first line contains an integer T, the number of test cases.
On the next T lines, you will be given an integer N.
Consider the family of all n-periodic functions for n in [1..N]. There are some links between some functions.
For example: [2, 0] = [2, 0, 1, 0] + [0, 0, 1, 0], with simplified notations.

### Output

Print the rank of this family ; ie the size of the largest collection of R-linearly independent elements of this family.

### Example

```Input:
3
2
3
4

Output:
2
4
6
```

### Constraints

```0 < T < 10^2
0 < N < 10^8
```

There's two input files, one easy (mostly small input), and a hard one (uniform random input).
My PY3.4 code get AC in 0.02+0.55=0.57s. This code isn't optimized. (edited 2017-02-11, after compiler changes)
I suspect there are several competitive approaches for this task.
Have fun ;-)

hide comments [Rampage] Blue.Mary: 2016-02-20 03:48:10 Some ugly technique... Francky: 2014-12-29 22:26:13 I plan 3 different trips with periodic functions. This one isn't easy, the next one should be easy, and the third very hard or extreme... If you find the image inappropriate, let's share, I can remove it.

 Added by: Francky Date: 2014-12-29 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 Resource: Own problem