— Народ, как вам такая задача?— Да норм.
BThero — волшебник, живущий в мире чудес. У него на столе находятся \(n\) кучек конфет. В \(i\)-й слева куче находится ровно \(a_i\) конфет. BThero умеет применять мощное заклинание копипаст:
- Он выбирает две произвольные кучки конфет \((i, j)\) такие, что \(1 \le i, j \le n\) и \(i \ne j\).
- Все конфеты из кучки с номером \(i\) копируются и вставляются в кучку \(j\). Более формально, выполняется операция \(a_j := a_j + a_i\).
BtHero может применять заклинание неограниченное количество раз — но, к сожалению, если в результате применения заклинания в какой-то куче станет строго больше, чем \(k\) конфет, волшебник теряет свои магические способности. Какое максимальное количество раз волшебник сможет применить заклинание, при этом не потеряв магические способности?
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество раз, которое волшебник BThero может применить свое заклинание.
Примечание
В первом наборе входных данных из условия после первого заклинания мы получим \(a = [1, 2]\) или \(a = [2, 1]\). В обоих случаях мы уже не сможем применить заклинание вновь, поскольку тогда потеряются наши магические способности.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 2
1 1
3 5
1 2 3
3 7
3 2 2
|
1
5
4
|