Problem:

For 1st row, element of a series is 1, for 2nd row, elements are 1,1,1. From 3rd row onwards, series increases by 1-1 elements at left and right of previous row such that each element is sum of 3 elements of above row(ie element immediately above and elements to left and right).

ie

1st row- 1

2nd row- 1 1 1

3rd row- 1 2 3 2 1

4th row- 1 3 6 7 6 3 1 (and so on)

Find the index of 1st element which is even for Nth row. Index starts with 1.

ie

1st row- 1

2nd row- 1 1 1

3rd row- 1 2 3 2 1

4th row- 1 3 6 7 6 3 1 (and so on)

Find the index of 1st element which is even for Nth row. Index starts with 1.

**Input Format:**

first line, T, contains number of test cases

T lines containing N**Output Format:**

Index of first even element for N

**Constraints:**

N>2

Sample Input

4

3

4

8

98

3

4

8

98

Sample Output:

2

3

3

4

2

3

3

4

Explanations:

for 4, series is 1 3 6 7 6 3 1, so 6 is first even number and index is 3.

for 4, series is 1 3 6 7 6 3 1, so 6 is first even number and index is 3.

Solution:

chomp($t=<STDIN>);

for($i=0;$i<$t;$i++)

{

chomp($n=<STDIN>);

if($n%2 == 1)

{

push(@out,2);

next;

}

$trd=$n*($n-1);

$trd=$trd/2;

if($trd % 2 eq 0)

{

push(@out,3);

next;

}

push(@out,4);

}

foreach(@out)

{

print "$_\n";

}

Tips:

If N is odd, answer is 2 always. 3rd elements is n(n-1)/2, check if this is even->answer is 3. Otherwise answer is 4 always.