Лука стоит перед рядом из \(n\) деревьев. У \(i\)-го дерева есть \(a_i\) фруктов и высота \(h_i\).
Он хочет выбрать непрерывный подмассив массива \([h_l, h_{l+1}, \dots, h_r]\), такой что для каждого \(i\) (\(l \leq i < r\)), \(h_i\) делится\(^{\dagger}\) на \(h_{i+1}\). Он соберет все фрукты с каждого дерева в подмассиве (то есть, он соберет \(a_l + a_{l+1} + \dots + a_r\) фруктов). Однако, если он соберет больше \(k\) фруктов в общей сложности, его поймают.
Какова максимальная длина подмассива, который Лука может выбрать, чтобы не попасться?
\(^{\dagger}\) \(x\) делится на \(y\), если отношение \(\frac{x}{y}\) является целым числом.
Выходные данные
Для каждого набора входных данных выведите одно целое число, длину максимального непрерывного подмассива, удовлетворяющего условиям, или \(0\), если такого подмассива нет.
Примечание
В первом примере Лука может выбрать подмассив с \(l=1\) и \(r=3\).
Во втором примере Лука может выбрать подмассив с \(l=3\) и \(r=4\).
В третьем примере Лука может выбрать подмассив с \(l=2\) и \(r=2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 12
3 2 4 1 8
4 4 2 4 1
4 8
5 4 1 2
6 2 3 1
3 12
7 9 10
2 2 4
1 10
11
1
7 10
2 6 3 1 5 10 6
72 24 24 12 4 4 2
|
3
2
1
0
3
|