B. Орак и модели
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В магазине есть $$$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\ (1 \le t\le 100)$$$: количество запросов.

Каждый запрос состоит из двух строк, в первой из которых записано одно целое число $$$n\ (1\le n\le 100\,000)$$$: количество моделей в магазине, а во второй записаны $$$n$$$ целых чисел $$$s_1,\dots,s_n\ (1\le s_i\le 10^9)$$$: размеры моделей.

Гарантируется, что сумма величин $$$n$$$ не превосходит $$$100\,000$$$.

Выходные данные

Выведите $$$t$$$ строк, в $$$i$$$-й из которых должно быть записано максимальное число моделей, которое Орак может купить для $$$i$$$-го запроса.

Пример
Входные данные
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
Примечание

Для первого запроса, например, Орак может купить модели с индексами $$$2$$$ и $$$4$$$, расстановка которых будет красивой так как $$$4$$$ делится на $$$2$$$ и $$$6$$$ больше, чем $$$3$$$. Рассмотрев остальные варианты, можно легко убедиться, что нет красивой расстановки с более, чем тремя моделями.

Во втором запросе Орак может купить модели с индексами $$$1$$$, $$$3$$$, и $$$6$$$. Рассмотрев остальные варианты, можно легко убедиться, что нет красивой расстановки с более, чем тремя моделями.

В третьем примере не существует красивой расстановки с более, чем одной моделью.