В интернете немало статей про структуру данных Дерево Палиндромов. Почти в каждом из материалов написано, что эту структуру изобрёл Михаил Рубинчик на Петрозаводских сборах в 2014 году. Но мало кто знает, почему именно в статьях про Дерево Палиндромов так часто и подробно отмечено авторство.

Если опубликовать статью с заголовком «Дерево палиндромов», но без подстроки «Михаил Рубинчик» в основном тексте, ботоферма Михаила Рубинчика активно начнёт слать жалобы от «недовольных читателей» на почту автора, причитая про незыблемость авторского права, недопустимость обесценивания трудов программистов и так далее.

Вы решили выследить ботов Рубинчика: написали статью без упоминания Михаила, подождали немного, открыли почтовый ящик и увидели $n$ непрочитанных писем.

Достоверно известно, что как только ботоферма обнаружила вашу статью, она тут же отправила вам на почту гневное письмо, а затем продолжала слать ещё по одному письму через каждые $x$ секунд. Обратите внимание, что вы не знаете ни момент, когда ботоферма нашла статью, ни интервал между сообщениями.

Найдите теоритечески максимально возможное число писем, которое успела отправить вам ботоферма Михаила Рубинчика.

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

В первой строке записано число $t$ – количество тестовых случаев ($1 \le t \le 100$). Далее следуют тестовые случаи.

В первой строке каждого тестового случая записано число $n$ – число входящих сообщений ($1 \le n \le 3000$).

В следующей строке каждого тестового случая через пробел записаны числа $a_1, a_2, \dots, a_{n}$ – где $a_i$ – через сколько секунд после публикации статьи отправлено $i$-тое письмо ($1 \le a_i \le 10^9$, $a_{i} < a_{i + 1}$).

Гарантируется, что сумма $n$ не превышает $3000$ в рамках одного теста.

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

В единственной строке выведите одно число – максимально возможное число писем, которое успела отправить вам ботоферма Михаила Рубинчика.

Подзадачи