The sequence of integers is given. Divide by 3 each its element that is divisible by 3.

Input

The first line contains the number of sequence elements n (n ≤ 100). In the second line the sequence elements are given, each of them does not exceed 100 by absolute value.

Output

Print n numbers in one line - the new elements of sequence, in the order they were given.