Алгоритмы

В стране из предыдущей задачи много специалистов не только по защите детей, но и про проектированию городов. Поэтому, чтобы решить проблему пробок в перенаселенной столице раз и навсегда, было решено построить новую столицу и перенести все правительство туда. Сказано — сделано.

Улицы в новой столице образуют правильную прямоугольную сетку, в которой все улицы пересекаются ровно через одну местную единицу длины. Вертикально идущие улицы называются улицами, а горизонтально идущие — аллеями. Всего в городе получилось 2000 улиц и 2000 аллей, поэтому, чтобы не придумывать много новых названий, их все просто пронумеровали. Улицы пронумеровали с запада на восток числами от −1000 до 999, а аллеи — с юга на север, тоже числами от −1000 до 999. Центром города считаются кварталы на пересечении улиц и аллей с номерами от −100 до 100.

Чтобы увеличить пропускную способность дорог в городе, было решено сделать все улицы и аллеи односторонними. По улицам с четными номерами разрешается ехать только с севера на юг, а по улицам с нечетными номерами — только с юга на север. Аналогично, по аллеям с четными номерами можно ехать только с востока на запад, а с нечетными — только с запада на восток.

Сколько местных единиц длины придется проезжать мэру новой столицы каждый вечер, возвращаясь из мэрии города домой? И мэрия, и дом мэра находятся в центре города. Мэр едет домой кратчайшим путем, соблюдая, впрочем, правила дорожного движения.

Входные данные
В первой строке даны два числа x1 и y1 — номер улицы и номер аллеи, на пересечении которых находится мэрия. В второй строке даны два числа x2 и y2 — номер улицы и номер аллеи, на пересечении которых находится дом мэра. Все числа целые и не превосходят по модулю 100.

Выходные данные
Выведите одно число: длину кратчайшего пути от мэрии до дома мэра на автомобиле.-
 

Примеры

№	Входные данные	Выходные данные
1	0 0 1 1	4
2	3 5 2 4	4

Когда настала зима и дел в Простоквашино стало мало, Шарик и Матроскин все дни проводили за настольными играми. Но шахматы, шашки, крестики-нлоики и домино им быстро надоели, а других игр у них не было. Поэтому они придумали новую игру.

Они выписывают на печке угольком 100 чисел. Потом по очереди каждый из них выбирает число с правого или левого края, прибавляет его к своей сумме и стирает число. Начинает игру Матроскин. Он выигрывает, если сможет набрать сумму, не меньшую, чем Шарик. По заданным числам определите, кто выиграет при оптимальной игре.

Входные данные
В единственной строке записаны через пробел 100 чисел a_i (1≤a_i≤1000)

Выходные данные
В ответ выведите Matroskin, если выигрывает Матроскин, иначе выведите Sharik. Если выигрывает Матроскин, то на следующей строке выведите оптимальный первый ход Матроскина: если он должен взять самое левое число, то выведите «left», если он должен взять самое правое число — выведите «right». Если Матроскину не важно, какое из чисел взять, выведите любое из слов «left» и «right».

Примеры

№	Входные данные	Выходные данные
1	1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2	Matroskin right

Начались каникулы, и дядя Фёдор, изрядно соскучившись по своим школьным друзьям, пригласил их всех в гости к себе в Простоквашино. После некоторых раздумий n из них согласились приехать. Взяв с собой все необходимые для отдыха на природе вещи, они приехали на вокзал покупать билеты. Выяснилось, что в поездах, идущих до Простоквашино, есть только купейные вагоны. В каждом вагоне всего k₄ четырехместных купе и k₂ — новых двухместных купе. Кроме друзей дяди Фёдора, никто не хочет ехать в Простоквашино, поэтому все места в поезде пока свободны. Друзья решили, что они хотят поехать все в одном вагоне: вместе ведь веселее. Чтобы поездка запомнилась надолго, один из друзей дяди Фёдора, Женя, решил одолжить у папы фотоаппарат «Зенит» и сфотографировать всех участников поездки, сидящих каждый на своем месте в поезде, по одному снимку на купе. Но пленка дорогая, а проявка — это долго и нудно, поэтому Женя попросил купить билеты так, чтобы вся дружная компания занимала как можно меньше купе. Помогите Жене посчитать, сколько в лучшем случае ему понадобится кадров, чтобы сфотографировать всю компанию, то есть посчитайте, сколько минимально купе они должны занять.

Входные данные
В первой и единственной строке вводятся числа n, k₄ и k₂ — количество друзей дяди Фёдора, едущих в Простоквашино, количество четырехместных купе в вагоне и количество двухместных купе в вагоне соответственно (1≤n≤10¹⁸, 0≤k₄≤10¹⁸, 0≤k₂≤10¹⁸).

Выходные данные
Выведите одно целое число — минимальное количество купе, в которых можно разместить всех друзей дяди Фёдора. Если же разместить всех друзей в одном вагоне не получится, выведите −1.

Примеры

№	Входные данные	Выходные данные
1	10 5 3	3

Однажды утром во время традиционной инспекции картофельного поля кот Матроскин обнаружил на одном из кустиков колорадского жука. Придя в ужас, он тут же помчался расспрашивать дядю Фёдора (как наиболее образованного из друзей) о том, как эти жуки размножаются и как с ними бороться.

Картофельные поля обычно очень аккуратно устроены: кусты картофеля рассажены на них так, что образуют клетчатое поле, где каждая клетка — картофельный куст. Как только на каком-то из кустов появляется колорадский жук, он начинает активно есть и размножаться. Поэтому каждый час на каждый куст будет добавляться столько же жуков, сколько соседних с ним по стороне кустов, уже зараженных жуками. Например, если у куста ровно один сосед, на котором уже есть жуки, то на него добавится один жук, а если все четыре соседа заражены жуками, то на куст добавится четыре новых жука. И если жуков не остановить, они заполнят собой все поле. Но к счастью, когда-то давно дядя Фёдор, прочитав статью в «Мурзилке», сделал отпугиватель колорадских жуков...

Если честно, Матроскин не очень понял, как работает этот отпугиватель. Но главное он запомнил: его надо установить на один из кустиков картофеля, и как только на этом кустике окажется ровно k колорадских жуков, что-то (вот этого Матроскин и не понял) произойдет и все жуки сбегут с поля.

Зная координаты куста картофеля, на который Матроскин установил отпугиватель, посчитайте, через сколько часов после появления первого колорадского жука на поле он подействует. Матроскин поставил ловушку в первый час после появления жука на поле.

Входные данные
Вам даны три числа: x и y — координаты кустика картофеля, на который Матроскин установил отпугиватель, и k — параметр отпугивателя (1<=k<=10⁹, |x|<=10⁹, |y|<=10⁹  ). Тот из кустов, на котором был найден первый жук, имеет координаты (0, 0) . Координаты всех кустов поля не превосходят 10⁹+1 по модулю.

Выходные данные
Выведите одно целое число: через сколько часов ловушка сработает. Если же ловушка никогда не сработает, выведите −1.

Примеры

№	Входные данные	Выходные данные
1	0 0 1	0
2	0 0 5	2

Приближалось лето, и Игорь, Гена и Денис решили пойти вместе в поход, как и в прошлом году. Почти все вопросы уже были решены: уже был проработан маршрут, куплены билеты на поезд, в шкафу у Дениса найдена четырехместная палатка, а под кроватью у Игоря — топор. Осталось решить только вопрос с продуктами.

В прошлом году ребята честно признались, что не знают, сколько им нужно продуктов, и попросили помочь свою одноклассницу Настю, которая составила им список покупок. Но в этом году снова спрашивать у нее уже как-то несолидно. Можно было бы посмотреть, сколько они покупали в прошлом году, и взять столько же, но ни у кого из ребят не сохранилось ни чеков, ни списка продуктов.

Зато у них сохранилась переписка в социальной сети, где они спорили, кто сколько банок тушенки понесет. В этой переписке Игорь сначала предложил поделить всю тушенку в отношении a: b: c, так, что первую часть понесет сам Игорь, вторую — Гена, а третью — Денис. Но Денису это не понравилось, и он предложил поменять соотношение на d: e: f.

Еще немного подумав, ребята поняли, что разрезать банки с тушенкой они все-таки не стали бы, и, значит, оба отношения были подобраны так, что у каждого в обоих случаях получалось целое число банок.

По данным двум отношениям a: b: c и d: e: f вычислите, сколько банок тушенки ребята покупали для прошлогоднего похода. Из всех возможных ответов выведите минимальный. Ребята помнят, что как минимум одна банка тушенки у них точно была.

Входные данные
В первой строке даны три целых положительных числа a, b, c, разделенные пробелами. Во второй строке даны три целых положительных числа d, e, f, также разделенные пробелами.

Все числа не превышают 1000.

Выходные данные
Выведите целое положительное число — количество банок тушенки.
 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	10 3 7 3 1 1	20	При делении тушенки между ребятами в отношении 10:3:7 Игорь понесет 10 банок, Гена — 3 банки, а Денис — 7 банок. А в случае соотношения 3:1:1 Игорю достанется 12 банок, а Гене и Денису по 4.

В числе подсчитали количество единиц, в получившемся опять подсчитали количество единици т.д.
Например: 111211121112111 - 12 - 1 - 1 - 1 - ...

В итоге полученная последовательность стабилизировалась. На каком числе?

Например, последовательность 111211121112111 - 12 - 1 - 1 - 1 - ... стабилизировалась на числе 1.

Входные данные
Вводится одно натуральное число, состоящее из не более чем 100 цифр.

Выходные данные
Выведите число, на котором стабилизировалась последовательность.

Примеры

№	Входные данные	Выходные данные
1	12345	1
2	2007	0

В некоторой карточной игре используется колода, в которой 4 туза. В игре принимает участие 4 игрока, каждому из которых раздается равное число карт, а две карты откладываются в прикуп.

Каждый игрок похвастал, сколько у него тузов. Определите, сколько игроков заведомо солгали.

Например, они сказали 1, 1, 1, 2. Следовательно, заведомо солгал 1 игрок. (Какие-то трое могли сказать правду, но все четверо правду сказать не могли, так как тузов всего 4).

Входные данные
Вводятся 4 числа (от 0 до 9 каждое), разделенных пробелом – количество тузов по словам первого, второго, третьего и четвертого игроков.

Выходные данные
Выведите одно число – минимальное количество игроков, которые заведомо солгали. Если все одновременно могли сказать правду, выведите число 0.

Примеры

№	Входные данные	Выходные данные
1	1 1 1 2	1
2	1 1 1 1	0

Представьте число 2011 в виду суммы K последовательных простых чисел (то есть простых чисел, между которыми нет других простых чисел). Например, число 31 можно представить в виде суммы трех посдедовательных простых чисел следующим образом: 7 + 11 + 13 = 31.

Входные данные
Вводится одно натуральное число K (от 1 до 2011).

Выходные данные
Выведите слагаемые в порядке возрастания, разделяя их пробелом.

Если разложить в сумму K слагаемых невозможно, выведите NO SOLUTION (заглавными буквами).

Примеры

№	Входные данные	Выходные данные
1	3	661 673 677
2	2	NO SOLUTION

По кругу записано несколько букв (возможно, повторяющихся). Петя интересуется, сможет ли он прочитать некоторое слово, если будет двигаться по кругу (в каком-либо направлении), не пропуская буквы (откуда начинать, и в какую сторону двигаться, он может выбрать сам).

Входные данные
В первой строке записаны строчные латинские буквы в том порядке, в котором они расставлены по кругу по часовой стрелке. Буквы записаны без пробелов, их количество не меньше 1 и не больше 100.

Во второй строке записано слово, которое хочет найти Петя. Оно также состоит из строчных латинских букв и имеет длину от 1 до 100.

Выходные данные
Выведите YES заглавными латинскими буквами, если такое слово можно прочитать, двигаясь по кругу, и NO в противном случае.

Примеры

№	Входные данные	Выходные данные
1	abcdefg abd	NO
2	abcdg bag	YES
3	a aaa	YES

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [2385177; 2385437] простые числа. Выведите все найденные простые числа в порядке возрастания, слева от каждого числа выведите его номер по порядку (каждое число с номером выводите с новой строки). 

Разложение на простые множители числа 12 можно записать тремя способами:

  12=2·2·3=2·3·2=3·2·2

А сколькими способами можно записать разложение на простые множители числа N?

Входные данные
Вводится одно натуральное число N (2 <= N <= 1 000 ).

Выходные данные
Выведите одно число – количество различных записей разложения.

Примеры

№	Входные данные	Выходные данные
1	12	3
2	13	1

Будильник в сотовом телефоне можно настроить так, чтобы он звонил каждый день в одно и то же время, либо в указанное время в определенный день недели. Независимо можно настроить несколько будильников.

По информации о будильниках и текущему времени и дню недели определите, когда прозвонит очередной будильник.

Входные данные
В первой строке вводятся три числа, задающие текущее время: день недели (от 1 до 7), часы и минуты.

Во второй строке вводится одно натуральное число N, не превосходящее 100 – количество будильников.

В следующих N строках вводятся описания N будильников. Описание каждого будильника состоит из трех чисел: дня недели (число от 1 до 7 для понедельника,  …, воскресенья, соответственно, 0 – если будильник должен звонить каждый день), часов (от 0 до 23), минут (от 0 до 59).


Выходные данные
Выведите  через пробел три числа, задающие день недели, часы и минуты, когда прозвонит ближайший будильник.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 10 20 2 1 23 15 0 10 10	3 10 10
2	7 1 1 3 7 0 59 7 23 59 7 1 1	7 1 1	Во втором примере третий будильник будет звенеть в начальный момент времени.

В Московском метрополитене вновь появляются автоматы для продажи билетов. Вас просят написать программу, которая будет рассчитывать, какую сдачу и какими купюрами и монетами требуется выдать пассажиру.

Входные данные
Вводится сначала стоимость билета, который хочет приобрести пассажир, затем общее количество купюр и монет, которые он опустил в автомат, а затем достоинства каждой из этих купюр и монет. Входные данные записаны в одной строке и разделены пробелами. Известно, что сумма всех купюр больше, чем стоимость билета. Во всех тестовых примерах стоимость билета – натуральное число, не превосходящее 1 000 рублей, количество купюр и монет не более 50, достоинство каждой не превосходит 500 рублей. Общая сумма денег, опущенных в автомат покупателем, превосходит стоимость билета.

Выходные данные
Программа должна вычислить, какими купюрами и монетами можно выдать сдачу, и вывести достоинство каждой из этих купюр или монет в произвольном порядке. Автомат может выдавать сдачу купюрами в 10, 50, 100 и 500 рублей, а также монетами в 1, 2 и 5 рублей. Если решений несколько, требуется выдать одно любое из них. Если решений нет, требуется выдать текст:

Sorry! Our monetary system is not perfect!
Please, choose another way to pay!
Thank you!

Примеры

№	Входные данные	Выходные данные
1	100 1 500	50 100 100 100 50

У меня в прихожей стоят в ряд 20 тапочек – 10 левых и 10 правых. Приходя домой, я переобуваюсь и выбираю два тапочка – левый и правый, в которые мне удобнее всего засунуть ноги. Естественно, что левый тапочек должен стоять левее правого, и расстояние (количество других тапочек) между ними должно быть как можно меньше. Напишите программу, которая вычисляет, сколько же тапочек стоит между теми, которые мне удобнее всего надеть.

Входные данные
Вводится последовательность из 10 нулей и 10 единиц, записанных в некотором порядке. Единица соответствует левому тапочку, 0 – правому тапочку. Числа разделены пробелами.
Выходные данные
Программа должна вывести количество тапочек между самыми удобными тапочками, или -1, если таких нет.
 

Примеры

№	Входные данные	Выходные данные
1	1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0	0

На одном из московских вокзалов билеты продают N касс. Каждая касса работает без перерыва определенный промежуток времени по фиксированному расписанию (одному и тому же каждый день). Требуется определить, на протяжении какого времени в течение суток работают все кассы одновременно.

Входные данные
Сначала вводится одно целое число N (0 < N ≤ 1000).

В каждой из следующих N строк через пробел расположены 4 целых числа, первые два из которых обозначают время открытия кассы в часах и минутах (часы — целое число от 0 до 23, минуты — целое число от 0 до 59), оставшиеся два — время закрытия в том же формате. Числа разделены пробелами.

Время открытия означает, что в соответствующую ему минуту касса уже работает, а время закрытия — что в соответствующую минуту касса уже не работает. Например, касса, открытая с 10 ч. 30 мин. до 18 ч. 30 мин., ежесуточно работает 480 минут.

Если время открытия совпадает с временем закрытия, то касса работает круглосуточно. Если первое время больше второго, то касса начинает работу до полуночи, а заканчивает — на следующий день.

Выходные данные
Требуется вывести одно число — суммарное время за сутки (в минутах), на протяжении которого работают все N касс.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 1 0 23 0 12 0 12 0 22 0 2 0	120	Первая касса работает с часу до 23 часов, вторая – круглосуточно, третья – с 22 часов до 2 часов ночи следующего дня. Таким образом, все три кассы одновременно работают с 22 до 23 часов и с часу до двух часов, то есть 120 минут.
2	2 9 30 14 0 14 15 21 0	0	Первая касса работает до 14 часов, а вторая начинает работать в 14 часов 15 минут, то есть одновременно кассы не работают.
3	2 14 00 18 00 10 00 14 01	1	Вместе кассы работают лишь одну минуту – с 14:00 до 14:01 (в 14:01 вторая касса уже не работает).

Из шахматной доски по границам клеток выпилили связную (не распадающуюся на части) фигуру без дыр. Требуется определить ее периметр.

Входные данные
Сначала вводится число N (1 ≤ N ≤ 64) – количество выпиленных клеток. В следующих N строках вводятся координаты выпиленных клеток, разделенные пробелом (номер строки и столбца – числа от 1 до 8). Каждая выпиленная клетка указывается один раз.

Выходные данные
Выведите одно число – периметр выпиленной фигуры (сторона клетки равна единице).

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 1 1 1 2 2 1	8	Вырезан уголок из трех клеток. Сумма длин его сторон равна 8.
2	1 8 8	4	Вырезана одна клетка. Ее периметр равен 4.

Метрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до N. На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).

Напишите программу, которая по данному вам описанию метрополитена определит, с каким минимальным числом пересадок можно добраться со станции A на станцию B. Если данный метрополитен не соединяет все линии в одну систему, то может так получиться, что со станции A на станцию B добраться невозможно, в этом случае ваша программа должна это определить.

Входные данные
Сначала вводится число N — количество станций метро в городе (2≤N≤100). Далее следует число M — количество линий метро (1≤M≤20). Далее идет описание M линий. Описание каждой линии состоит из числа P_i — количество станций на этой линии (2≤P_i≤50) и P_i чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды).

Затем вводятся два различных числа: A — номер начальной станции, и B — номер станции, на которую нам нужно попасть. При этом если через станцию A проходит несколько линий, то мы можем спуститься на любую из них. Так же если через станцию B проходит несколько линий, то нам не важно, по какой линии мы приедем.

Выходные данные
Выведите минимальное количество пересадок, которое нам понадобится. Если добраться со станции A на станцию B невозможно, программа должна вывести одно число –1 (минус один).
 

Примеры

№	Входные данные	Выходные данные
1	5 2 4 1 2 3 4 2 5 3 3 1	0
2	5 5 2 1 2 2 1 3 2 2 3 2 3 4 2 4 5 1 5	2
3	10 2 6 1 3 5 7 4 9 6 2 4 6 8 10 7 3 8	1
4	4 2 2 1 2 2 3 4 1 3	-1

X мальчиков и Y девочек пошли в кинотеатр и купили билеты на подряд идущие места в одном ряду. Напишите программу, которая выдаст, как нужно сесть мальчикам и девочкам, чтобы рядом с каждым мальчиком сидела хотя бы одна девочка, а рядом с каждой девочкой — хотя бы один мальчик.

Входные данные
Вводятся два числа — X и Y (оба числа натуральные, не превосходящие 100).

Выходные данные
Выведите какую-нибудь строку, в которой будет ровно X символов B (обозначающих мальчиков) и Y символов G (обозначающих девочек), удовлетворяющую условию задачи. Пробелы между символами выводить не нужно. Если рассадить мальчиков и девочек согласно условию задачи невозможно, выведите строку NO SOLUTION.

Примеры

№	Входные данные	Выходные данные
1	5 5	BGBGBGBGBG
2	5 3	BGBGBBGB
3	100 1	NO SOLUTION

У Маши есть связный ненаправленный граф G с N вершинами, помеченными 1…N и M ребрами (\(1 \leq N \leq10^2\), \(N-1 \leq M \leq \frac {N^2+N}{2}\)). G может содержать петли (ребра из вершины в неё же), но не имеет параллельных ребер (несколько ребер, соединяющих одни и те же конечные точки).
Пусть \(f_G(a,b)\) это булевская функция, которая отвечает истина, если существует путь от вершины 1 до вершины a, который проходит ровно b ребер, для \(1 \leq a \leq N\) и \(0 \leq b\), и ложь иначе. Если по ребру проходим множество раз, это число включается в ответ. 
Даша хочет повторить за Машей. В частности, она хочет сконструировать ненаправленный граф G′ такой, что \(f_{G'}(a,b)=f_G(a,b)\) для всех a и b.

Посчитайте количество различных графов G′, которые Даша может создать, по модулю \(10^9+7\). Как и G, G′ может содержать петли но не может иметь параллельные ребра (это означает, что имеется всего \(2^{ \frac {N^2+N} {2}}\) различных графов на N вершинах).
Каждый ввод содержит T (\(1 \leq T \leq \frac {10^5}{4}\)) тестов, которые должны решаться независимо. Гарантируется, что сумма \(N^2\) по всем тестам не превысит \(10^5\).

Входные данные
Первая строка ввода содержит T, количество тестов.
Первая строка каждого теста содержит два целых числа N и M.
Следующие M строк каждого теста содержат два целых числа x и y (\(1 \leq x \leq y \leq N\)), обозначающих ребро между x и y в G.

Тесты разделены пустой строкой для читабельности.

Выходные данные
Для каждого теста выведите количество различных G′ по модулю \(10^9+7\) на отдельной строке.
 
 

Примеры

№	Входные данные	Выходные данные	Примечание
1	1 5 4 1 2 2 3 1 4 3 5	3	G′ может быть равен G′ или одному из двух следующих графов: 5 4 1 2 1 4 3 4 3 5 5 5 1 2 2 3 1 4 3 4 3 5
2	7 4 6 1 2 2 3 3 4 1 3 2 4 1 4 5 5 1 2 2 3 3 4 4 5 1 5 5 7 1 2 1 3 1 5 2 4 3 3 3 4 4 5 6 6 1 2 2 3 3 4 4 5 5 6 6 6 6 7 1 2 2 3 1 3 1 4 4 5 5 6 1 6 10 10 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 22 28 1 2 2 3 3 4 4 5 5 6 6 7 1 7 1 8 3 9 8 10 10 11 10 12 10 13 10 14 11 15 12 16 13 17 14 18 9 15 9 16 9 17 9 18 15 19 19 20 15 20 16 21 21 22 16 22	45 35 11 1 15 371842544 256838540	Это пример более крупного теста. Обязательно выводите ответ по модулю \(10^9+7\). Обратите внимание, что ответ для предпоследнего теста - \(2^{45}\ \ (mod\ 10^9 + 7)\).

 

Маша и Даша играют в игру с N (\(1<=N<=10^5\)) кучками камушков, где i-ая кучка содержит ai камешков (\(1<=i<=N\), \(1<=a_i<=10^6\)). Они ходят по очереди, первой ходит Маша.

• Сначала Маша выбирает некоторое положительное число s1 и удаляет s1 камешков из некоторой кучки, в которой есть не менее s1 камешков.
• Затем Даша выбирает некоторое положительное число s2 такое, что s2 делится на s1 и удаляет s2 камешков из некоторой кучки, содержащей не менее s2 камешков.
• Затем Маша выбирает некоторое положительное число s3, которое делится на s2 и удаляет s3 камешков из некоторой кучки, в которой есть не менее s3 камешков.
• В общем случае si, количество камешков, которое убирается на ходу i, должно быть делителем si+1.

Проигрывает тот, кто не может сделать ход.

Вычислите количество способов, которыми Маша может удалить камешки на первом ходу для того, чтобы гарантировать себе победу (то есть существет стратегия, используя которую Маша победит вне зависимости от ходов Даши). Два способа удаления камешков называются различными, если они удаляют различное количество камушков или они удаляют камешки из различных кучек.

Входные данные
Первая строка содержит N.
Вторая строка содержит N разделённых одиночными пробелами целых чисел a1,…,aN.


Выходные данные
Выведите количество способов, которыми Маша может удалить камушки на первом ходу, чтобы гарантировать себе выигрыш.
Для вычислений используйте 64-ное целое например, "long long" в C/C++.
 
 

Примеры

№	Входные данные	Выходные данные	Примечание
1	1 7	4	Маша выбирает 4, 5, 6, 7 камушков из одной кучи и игра закончится сразу.
2	6 3 2 3 2 3 1	8	Маша выиграет, если удалит 2 или 3 камушка из любой кучи. Затем игроки будут по очереди брать одно и то же количество камушков, но Маша сделает последний ход.