Что может быть проще простого числа? Казалось бы, объяснить, что такое простое число, можно даже человеку, совершенно далёкому от математики: целое число называется простым, если оно не меньше двух и не делится ни на какое целое положительное число, кроме единицы и самого себя. Это определение будет понятно даже третьекласснику, только-только познакомившемуся с делением. Что может быть проще? Но, как часто случается в математике, за кажущейся простотой определения скрывается очень глубокая теория с множеством нетривиальных фактов, многие из которых остаются недоказанными и по сей день.

Прочитав популярную книгу Д. Дербишира «Простая одержимость» , Леопольд узнал следующий занятный факт. Оказывается, существует Теорема о распределении простых чисел , гласящая, что количество простых чисел, не превышающих N , можно очень точно оценить как . Например, начиная с N > 5000 , эта формула даёт ошибку, не более чем в 15% от реального значения. Более того, с ростом N относительная погрешность такой оценки падает, стремясь к нулю.

Леопольд крайне заинтересовался простыми числами и связанной с ними теорией. Он решил выдвинуть какую-нибудь не менее важную и серьёзную гипотезу, а потом доказать её, и назвать полученный факт теоремой Леопольда. Для этого ему нужна помощь в отыскании закономерностей, описывающих простые числа. Он просит вас написать для него программу, которая ищет для него Q отрезков, i -й из которых состоит из L _i последовательных натуральных чисел и содержит определённое количество K _i простых чисел. Для простоты анализа он просит вас ограничиться в поисках первыми десятью миллионами чисел. Помогите ему, и, возможно, вам с ним удастся оставить след в истории!

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

К счастью, завод сотрудничает с союзом художников по матрёшкам. В частности, был заключён договор, позволяющий заводу заказывать роспись матрёшек. В договоре указано, что матрёшка — это упорядоченный набор из M статуэток ( 1 ≤ M ) размеров a ₁ , a ₂ , ..., a _M , где a ₁ + 1 = a ₂ , a ₂ + 1 = a ₃ , ..., a _{M - 1} + 1 = a _M . Там же прописано, что стоимость раскрашивания одной матрёшки равна одному тугрику, при этом количество статуэток, входящих в матрёшку, значения не имеет.

Получается, что для того чтобы продать всё содержимое склада, нужно сначала собрать заготовки в матрёшки и заказать роспись полученных матрёшек у художников. Помогите директору завода сделать это, потратив как можно меньше тугриков!

В одном уездном городе Эн было решено построить собственное метро. Все силы города были мобилизованы на выкапывание станций и прокладку подземных путей дедовскими лопатами.

Вся эта история нас бы совершенно не интересовала, если бы однажды в мэрию города не пришло письмо из далёкой страны Емакира. Оказалось, что компания Alpep подозревает администрацию уездного города в нарушении их патента на jMetro и грозится возбудить против города Эн дело. Согласно патенту, jMetro — это метро, в котором:

• существует ровно одна узловая станция, в которой начинаются все радиальные линии метро, и это единственная станция, принадлежащая хотя бы двум радиальным линиям;
• существует ровно одна кольцевая линия, все станции которой лежат на радиальных линиях, причём на каждой радиальной линии лежит ровно одна станция кольцевой линии;
• кольцевая линия не проходит через узловую станцию;
• кольцевая линия не проходит через конечные станции радиальных линий.

Поскольку компания Alpep известна своими необоснованными обвинениями в нарушениях патентов, мэрия города хочет проверить правомочность заявления компании.

Лена - страстная любительница пасьянсов. Больше других ей нравятся стандартные пасьянсы на её стареньком рабочем компьютере под управлением доисторической операционной системы <<вай-вай-вай-крософт миндоус XP>>, из которых особенное предподчтение она отдаёт <<Свободной ячейке>> (другое название этого пасьянса - <<Солитер>>). Все стандартные расклады уже давно решаются Леной за минуту, поэтому в свободное время она придумывает, как бы усложнить правила игры.

Она предлагает вам помочь ей со следующей постановкой. В её игре участвуют \(K\) карт одной масти достоинствами от \(1\) до \(K\). Изначально они лежат в одном из слотов в следующем порядке при перечислении снизу вверх: \(1, K, K - 1, K - 2, \dots, 3, 2\). Цель её пасьянса - переложить все карты кроме единицы в один из свободных слотов в порядке \(K, K - 1, \dots 3, 2\), используя \(N\) дополнительных свободных слотов для стопок и \(F\) слотов для одиночных карт.

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

Лена не может определиться с тем, сколько именно карт может лежать в изначальной стопке и сколько должно быть слотов каждого вида. Она просит вас определить для некоторых наборов \(N\), \(F\) и \(K\), раскладывается ли пасьянс.