После изучения изучения маяков Мистер Б загорелся желанием самому отправиться на планету инопланетян, ведь он узнал про них очень важную информацию: они живут в системе с мерцающей звездой, названной Луной. Более того, Мистеру Б стало известно, что данная звезда мерцает раз в T секунд. Но вот незадача: ученые еще не открыли данную звезду, хотя во всю стараются решить данную проблему.
Над поиском данной звезды бьются n астрономов, пронумерованных от 1 до n и наблюдающих за ней посредством отправки запросов на съемку неба. Каждый запрос есть запись неба в течение 1 секунды.
Астрономы посылают запросы по циклу: i-й астроном посылает запрос через ai секунд после (i - 1)-го (если предыдущий запрос послан в момент t, то текущий — в t + ai); 1-й астроном посылает запрос через a1 секунд после n-го. Можно считать, что первый запрос отправлен в момент времени 0 первым астрономом.
Первый момент вспышки звезды неизвестен, но очевидно, что все моменты вспышки звезды однозначно определяются ее моментом вспышки в отрезке [0, T). Более того, данный интервал можно разбить на T частей длиной по 1 секунде вида [t, t + 1), где t = 0, 1, 2, ..., (T - 1).
Астроном, открывший Луну, будет крайне занят, а потому Мистеру Б надо уже сейчас знать оценку успешности каждого астронома.
Для каждого астронома посчитайте, сколько существует интервалов [t, t + 1) (t = 0, 1, 2, ..., (T - 1)) в интервале [0, T) таких, что данный астроном первым обнаружит Луну, если первая вспышка звезды произойдет в этом интервале.
Примечание
В первом примере первый астроном будет посылать запросы в моменты t1 = 0, 5, 10, ..., второй — в моменты t2 = 3, 8, 13, .... Поэтому интервал [0, 1) первым изучит 1-й астроном в момент t1 = 0, [1, 2) — 1-й астроном в момент t1 = 5, [2, 3) — 1-й астроном в момент t1 = 10, а [3, 4) — 2-й астроном в момент t2 = 3.
Во втором примере интервал [0, 1) — 1-й астроном, [1, 2) — 2-й астроном, [2, 3) — 3-й астроном, [3, 4) — 4-й астроном, [4, 5) — 1-й астроном.