Sharmeen is a little girl and she can write only “one!”. If any one tells her to write 1, then she write “one”. If any one tells her to write 2, she write “one one!!”. If any one tells her to write 3, she write “one one one!!!”. If any one tells her to write 4, she write “one one one one!!!!”. So, The basic idea is, if someone tell her to write n, she will write “one” n times maintaining a space between any two consecutive “one” and then write n “!” marks.

Writing the same thing several time is boring, so she hired you to write a program for her which will do the same thing.

Input

First line will contain number of test cases t (1 <= t <= 50)

In each test case you will given an integer n (1 <= n <= 50000).

Output

For each test case print the expected output in one line.

Example

Input:
2
1
2

Output:
one!
one one!!