Problem Description

$\space \space$ *Desperate magic addiction once made us miserable. Territory occupied by natural disasters made us wandering. But the misery should be put behind and we shall enter a new chapter.*

$\space \space$ *Us the same blood flows,we will bring back the glory of the sun again!*

$\space \space$ *Salama ashal'anore!*

Kael'thas has a magic square which contains all points on the 2D plane whose coordinates are integers within $[0,n]$.

He can draw several straight fire lines on the plane. Each line will cover all the points on it. Note that the lines have no endpoints and extend to infinity in both directions.

And there is one special rule: he cannot draw a line that covers the point $(0,0)$ because his throne is on $(0,0)$.

What is the minimum number of lines he needs to draw so that the lines will cover all the points of the magic square except $(0,0)$?

Input

The input consists of multiple test cases.

The first line contains one integer $T\ (1\leq T\leq50)$ denoting the number of test cases.

The following are T test cases.

Each test case consists of one line containing one integer $n\ (0\leq n\leq 50)$.

Output

For each test case, output one line containing one integer indicating the answer.

1
2

4

Hint

One possible answer for the sample is : x = 1, x = 2, y = 1, y = 2