• First place: M. Prathab
• Second place: Ramesh Kumar P
• Third place: Kamalakannan AR

Given any name, write a program which can predict if it is a male name or a female name.

Input format

The first line N, is the number of names. This is followed by N lines each containing one name per line. Only first names will be provided and the names will not contain spaces.

Output format

The output must contain N lines. Line i is "male" if the i^th name is male, else it must be "female".

Sample Input

3
Arjun
Mallika
John

Sample Output

male
female
male

Constraints

N <= 5000
Time limit: 10 seconds
Memory limit: 64 MB

Scoring

Score = 100*(no. of correct answers)/N
Maximum score = 100
Maximum no. of submissions = 45

Define k-smooth number to be a number with all its prime factors <= k. Write a program to find the n-th 5-smooth number (modulo 100000007) in linear time.

Input format

The first line N, is the number of test cases. This will be followed by N integers, a₁, ..., a_n one per line.

Output format

The output must contain N lines. Line i is the a_i^th smooth number modulo 100000007.

Sample Input

3
1
4
56

Sample Output

1
4
320

Constraints

N, a_i <= 100000
Time limit: 4 seconds
Memory limit: 64 MB

Scoring

Score = 100*(no. of correct answers)/N
Maximum score = 100
Maximum no. of submissions = 45