У вас есть \(n\) лампочек, пронумерованных числами \(1, 2, \ldots, n\). Изначально все лампочки включены. Под инвертированием состояния лампочки подразумевается её выключение, если она была включена, и её включение, иначе.
Затем вы делаете следующее:
- для каждого \(i = 1, 2, \ldots, n\), инвертировать состояние всех лампочек \(j\), таких что \(j\) делится на \(i^\dagger\).
После выполнения всех операций некоторые лампочки по-прежнему будут включены. Ваша цель — сделать так, чтобы число таких лампочек было ровно \(k\).
Найдите наименьшее подходящее \(n\), такое что после выполнения всех операций включены будут ровно \(k\) лампочек. Можно показать, что ответ всегда существует.
\(^\dagger\) Целое число \(x\) делится на \(y\), если существует целое \(z\), такое что \(x = y\cdot z\).
Выходные данные
Для каждого набора входных данных выведите \(n\) — наименьшее число лампочек.
Примечание
В первом наборе входных данных наименьшее число лампочек равно \(2\). Будем записывать состояние всех лампочек в виде массива, где \(1\) соответствует включённой лампочке, а \(0\) — выключенной. Изначально массив равен \([1, 1]\).
- После выполнения операции с \(i = 1\), массив становится равен \([\underline{0}, \underline{0}]\).
- После выполнения операции с \(i = 2\), массив становится равен \([0, \underline{1}]\).
В итоге включена ровно \(k = 1\) лампочка. Можно показать, что ответ не может быть меньше \(2\).
Во втором наборе входных данных наименьшее число лампочек равно \(5\). Изначально массив равен \([1, 1, 1, 1, 1]\).
- После выполнения операции с \(i = 1\), массив становится равен \([\underline{0}, \underline{0}, \underline{0}, \underline{0}, \underline{0}]\).
- После выполнения операции с \(i = 2\), массив становится равен \([0, \underline{1}, 0, \underline{1}, 0]\).
- После выполнения операции с \(i = 3\), массив становится равен \([0, 1, \underline{1}, 1, 0]\).
- После выполнения операции с \(i = 4\), массив становится равен \([0, 1, 1, \underline{0}, 0]\).
- После выполнения операции с \(i = 5\), массив становится равен \([0, 1, 1, 0, \underline{1}]\).
В итоге включены ровно \(k = 3\) лампочки. Можно показать, что ответ не может быть меньше \(5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
3
8
|
2
5
11
|