У Доры есть множество \(s\), содержащее целые числа. Сначала она поместит все целые числа из отрезка \([l, r]\) в множество \(s\). То есть, целое число \(x\) изначально содержится в множестве тогда и только тогда, когда \(l \leq x \leq r\). Затем она позволяет вам выполнять следующие операции:
- Выберите три различных целых числа \(a\), \(b\) и \(c\) из множества \(s\), такие что \(\gcd(a, b) = \gcd(b, c) = \gcd(a, c) = 1^\dagger\).
- Затем удалите эти три целых числа из множества \(s\).
Какое максимальное количество операций вы можете выполнить?
\(^\dagger\)Напомним, что \(\gcd(x, y)\) означает наибольший общий делитель целых чисел \(x\) и \(y\).
Примечание
В первом наборе входных данных вы можете выбрать \(a = 1\), \(b = 2\), \(c = 3\) в единственной операции, так как \(\gcd(1, 2) = \gcd(2, 3) = \gcd(1, 3) = 1\), в множестве больше нет целых чисел, поэтому больше операций выполнить нельзя.
Во втором наборе входных данных вы можете выбрать \(a = 3\), \(b = 5\), \(c = 7\) в единственной операции.
В третьем наборе входных данных вы можете выбрать \(a = 11\), \(b = 19\), \(c = 20\) в первой операции, \(a = 13\), \(b = 14\), \(c = 15\) во второй операции и \(a = 10\), \(b = 17\), \(c = 21\) в третьей операции. После трех операций множество \(s\) содержит следующие целые числа: \(12\), \(16\), \(18\). Можно доказать, что нельзя сделать больше \(3\) операций.