Description

Your friend likes walking up stairs.
He likes walking up stairs so much that everytime, he attempts to walk up stairs in a way he never did before.
When walking up stairs, he either takes one step up or three steps up at once.
Specifically, given a staircase with N levels, he would decide a sequence of steps (composed of 1s and 3s) to take, such that the sum of the sequence is N.

Two ways of walking up stairs are different if and only if the sequence of steps differ.

For example, given a stairs with 5 floors, he has 4 unique ways of walking up the stairs:
a. [1, 1, 3]
b. [1, 3, 1]
c. [3, 1, 1]
d. [1, 1, 1, 1, 1]

Given N, find out how many times your friend may enjoy walking the stairs up in a unique way.

Smart as your friend is, figured out that f(n), the number of ways to walk up n levels, may be described as the following:

f(n) = f(n - 1) + f(n - 3), if n > 2
f(n) = 1, otherwise

Input

N

(N is a positive integer in between 1 and 116)

Output

A positive integer indicating the number of unique ways to walk up the stairs, with a trailing newline character.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There's an old game called He loves me... he loves me not. The person picks petals from the flower thinking about a special someone. At the end if the number of picked petals is odd the special someone is in love.

However, you ain't got no flowers, so you will be deciding if the number of factors of N is odd the special someone is in love.

For example, if N is 28, the factors are 1, 2, 4, 7, 14, 28, so the special someone is not in love.
However, if N is 4, the factors are 1, 2, 4, so the special someone is in love.

In order to prevent you from cheating, you will need to output results for a batch of Ns in each testcase.

Input

T
N_1
N_2
...
N_T

 

(In the first line there is T, a positive integer not exceeding 100)
(T lines follows, the i'th line containing N_i, a positive integer not exceeding 1000000000,  corresponding to the settings of the i'th query)

Output

T lines, the i'th line with the answer to the i'th query (an integer 0 if the someone is not in love and 1 otherwise), followed by a newline character

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In general, using ALL CAPITAL LETTERS is considered rude, and may be interpreted as screaming or shouting in written text.

ALSO, IT SEEMS A LITTLE HARDER TO READ.

Given dialogues that are writen in all-caps, you've decided to transform them to all-lowercase.

Input

A string consisting of only capital letters, whose length does not exceed 100.

Output

A string consisting of only lowercase letters, followed by a newline character.

Sample Input  Download

Sample Output  Download

Tags

Discuss