개구리

호수에 연꽃잎이 한 줄로 끝없이 놓여 있다. 잎에는 한쪽 끝에서부터 1번, 2번, 3번, 이렇게 번호가 붙어 있고, 개구리들은 매일 이 잎 위에서 쉰다. 아침마다 개구리는 다음 규칙에 따라 자리를 잡는다.

• 개구리의 종류는 $N$가지이고, 1번부터 $N$번까지 번호가 붙어 있다. 각 종류의 개구리가 호수에 몇 마리 사는지 주어진다.
• $d$번 종류의 개구리는 한 번에 정확히 잎 $d$개만큼 뛴다. 먼저 $d$번 잎으로 뛰고, 그다음에는 $2d$번, 그다음에는 $3d$번으로 옮겨 가며, 다른 개구리가 없는 잎에 닿을 때까지 계속 뛴다. 그 잎에 닿으면 하루가 끝날 때까지 머문다.
• 개구리는 한 마리씩 차례로 호수에 온다. 1번 종류가 모두 먼저 오고, 그다음 2번 종류가 모두 오며, 같은 방식으로 $N$번 종류까지 이어진다.

아래 그림은 첫 번째 입력 예제를 그린 것이다. 종류가 세 가지이고 종류마다 두 마리씩 산다. 0은 빈 잎이고, 나머지 숫자는 그 잎에 머문 개구리의 종류다. 회색 잎은 가장 마지막에 온 개구리가 자리를 잡기까지 거쳐 간 잎이다.

마지막 1번 개구리는 2번 잎, 마지막 2번 개구리는 6번 잎, 마지막 3번 개구리는 9번 잎에 있다.

각 종류마다 그 종류의 개구리가 머문 잎 중 가장 먼 잎의 번호를 구하는 프로그램을 작성하라.

첫째 줄에 개구리 종류의 수 $N$이 주어진다. ($1 \le N \le 10$)

다음 $N$개의 줄에는 1번 종류부터 $N$번 종류까지 순서대로, 그 종류의 개구리 수가 한 줄에 하나씩 주어진다. 각 수는 50000000 이하의 자연수다.

$N$개의 줄에 1번 종류부터 $N$번 종류까지 순서대로, 그 종류의 개구리가 머문 잎 중 가장 먼 잎의 번호를 한 줄에 하나씩 출력한다.