Internet Problem Solving Contest

• Input data set – G

One day, Mrs. Goa Waymaths was chosen to be the substitute teacher in a class full of young maths enthusiasts. In order to keep the kids quiet and busy, she gave each of them a deck of cards and asked them to play a game of solitaire she used to play when she was in their age.

The game is very simple. You get a deck of 20 cards, numbered 1 to 20, and place them all on the table. Your goal is to pick up as many cards as possible. There is only one requirement: You are not allowed to pick up a card, if it would lead to a situation where you hold three cards with numbers A, B and C such that A+B=C. (For example, out of the cards 4, 5 and 9 you may only pick at most two.)

One of the best students in the class, little William Strathmore Xaverol (known as Johnny among friends), considered the game too simple. Instead of playing with 20 cards he started to play it with N (virtual) cards, numbered 1 to N. Soon, he found the maximal number of cards he can pick up.

Once he had the answer, he posed a more difficult question: in how many different ways can he take that maximum number of cards? (Order in which he picks them up doesn't matter.)

For example, if N=3, he can't pick up all three cards (because 1+2=3), but he can pick up any two cards. There are three ways of selecting two out of three cards (1 and 2, 1 and 3, 2 and 3). Thus the answer to Johnny's "hard" question for N=3 is 3.

Problem specification (G1)

In the easy subproblem (G1), your task is to determine the maximum number of cards one can take without breaking the aforementioned rule.

Problem specification (G2)

In the hard subproblem (G2), your task is to determine the number of distinct sets of cards having the maximal possible cardinality (= count of elements) and satisfying the rules of the game.

Input specification

The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of one line containing one integer N.

For both subproblems use the same input file.

Output specification

For each test case output a line containing a single number – the answer to the particular test case.

Example

Input:

2

1

3

Output (G1):

1
2

Output (G2):

1
3

---

Credits:
Problemsetter(s): g00ber
Contest-related materials: g00ber, yulka