В магазине есть \(n\) моделей, пронумерованных от \(1\) до \(n\), размеры которых равны \(s_1, s_2, \ldots, s_n\).
Орак купит некоторые из этих моделей и упорядочит их по возрастанию номеров (индексов, а не размеров).
Орак считает, что полученная расстановка красивая, если для любых двух соседних моделей с номерами \(i_j\) и \(i_{j+1}\) (обратите внимание, что \(i_j < i_{j+1}\), так как Орак упорядочил их правильно), \(i_{j+1}\) делится на \(i_j\) и \(s_{i_j} < s_{i_{j+1}}\).
Например, для \(6\) моделей с размерами \(\{3, 6, 7, 7, 7, 7\}\), он может купить модели с индексами \(1\), \(2\), и \(6\), и полученная расстановка будет красивой. Обратите внимание, что расстановка из одной модели также считается красивой.
Орак хочет знать, какое наибольше число моделей он может купить, и он может задавать вам эти вопросы по несколько раз.
Выходные данные
Выведите \(t\) строк, в \(i\)-й из которых должно быть записано максимальное число моделей, которое Орак может купить для \(i\)-го запроса.
Примечание
Для первого запроса, например, Орак может купить модели с индексами \(2\) и \(4\), расстановка которых будет красивой так как \(4\) делится на \(2\) и \(6\) больше, чем \(3\). Рассмотрев остальные варианты, можно легко убедиться, что нет красивой расстановки с более, чем тремя моделями.
Во втором запросе Орак может купить модели с индексами \(1\), \(3\), и \(6\). Рассмотрев остальные варианты, можно легко убедиться, что нет красивой расстановки с более, чем тремя моделями.
В третьем примере не существует красивой расстановки с более, чем одной моделью.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
5 3 4 6
7
1 4 2 3 6 4 9
5
5 4 3 2 1
1
9
|
2
3
1
1
|