XYZ supermarket system has many members. Each member has a membership card. Membership card is linked to one of classes, updated automatically when the total purchase value reaches the specified threshold:

• Starter: The total purchase value of ~1~ million VND or more

• Gold: The total purchase value of ~20~ million VND or more

• Diamond: The total purchase value of ~50~ million VND or more

• Platinum: The total purchase value of ~200~ million VND or more

When buying a new item, members will receive a discount on the sale price according to the membership card:

• Starter: ~2\%~ discount

• Gold: ~3\%~ discount

• Diamond: ~5\%~ discount

• Platinum: ~7\%~ discount

Please implement the program to calculate the amount of discount for each purchase of customers.

Input

• The first line contains the number ~n~, which is the number of items purchased ~(n ≤ 10^5)~

• The next line contains ~n~ integers, corresponding to the selling price of ~n~ products in the correct order of purchase time

Output

Print in chronological order the amount of discount for ~n~ products, the resulting output separated by spaces

Example Input

5
500000 2000000 6000000 50000000 3000000

Example Output

0 0 120000 1000000 150000

Note

• The answer has an error margin between the results of no more than ~10^{-5}~.