Frogs

Time limit1sMemory limit128 MB

Summary

Frogs of type d land on pads d, 2d, 3d, ... stopping at the first pad with no other frog; find the farthest occupied pad for each type.

Level: Hard8 of 10
Topics: Number theory, Math, Brute force, Implementation
Solved: No attempts yet

Problem

An endless row of lily pads floats on a lake. The pads are numbered 1, 2, 3, and so on from one end, and frogs rest on them every day. Each morning the frogs take their places by the following rules.

There are $N$ types of frogs, numbered 1 to $N$ . For every type, the number of frogs of that type living on the lake is known.
A frog of type $d$ jumps exactly $d$ pads at a time. It jumps first to pad $d$ , then to pad $2d$ , then to pad $3d$ , and it keeps going until it lands on a pad that holds no other frog. It stays on that pad until the end of the day.
The frogs arrive one at a time. Every frog of type 1 arrives first, then every frog of type 2, and so on up to type $N$ .

The picture below draws the first sample input, where there are three types and two frogs of each type. A zero is an empty pad, and every other number is the type of the frog resting on that pad. The shaded pads are the ones the newest frog passed on its way to the pad it settled on.

The last frog of type 1 sits on pad 2, the last frog of type 2 on pad 6, and the last frog of type 3 on pad 9.

Write a program that finds, for each type, the number of the farthest pad holding a frog of that type.

Input

The first line contains the number of frog types $N$ ( $1 \le N \le 10$ ).

Each of the next $N$ lines contains the number of frogs of one type, one per line, from type 1 to type $N$ . Each of those numbers is a positive integer no greater than 50000000.

Output

Print $N$ lines. For each type from 1 to $N$ , in order, print the number of the farthest pad holding a frog of that type, one per line.

Examples3

Example 1
Input
```
3
2
2
2
```
Expected output
```
2
6
9
```

Example 2

Input

Expected output

10000000
30000000
50000001

Example 3
Input
```
5
1
5
5
2
1
```
Expected output
```
1
10
18
20
5
```