Mr T có một mảng \(a\) có độ dài là \(n\). Mr T cho Huy \(n\) bảng copy của mảng \(a\) được viết liền kề nhau tạo thành 1 mảng \(b\) mới và Mr T đố Huy rằng độ dài dãy con tăng dài nhất của mảng \(b\) mới được tạo thành là bao nhiêu?

Lưu ý dãy con tăng dài nhất là dãy con bắt buộc phải có thứ tự tăng dần, \([1,2,2,3,4]\) không phải là một dãy con tăng dài nhất nhưng \([1,2,3,4,5]\) là một dãy con tăng dần.

Input:

• Dòng đầu đầu số nguyên \(t\) là số lượng test case.
• Dòng đầu tiên của mỗi test case chứa 1 số nguyên \(n\) \((1 \le n \le 10^3).\)
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...a_n\) được cách nhau bởi dấu cách \((1 \le a_i \le 10^9).\)

Output:

• Mỗi test case in ra một số nguyên là độ dài của mảng con tăng dài nhất trong mảng \(b\).

Example:

Sample input:

2
3
3 2 1
6
3 1 4 1 5 9

Sample output:

3
5

Giải thích:

Ở test case thứ nhất, mảng \(b\) được tạo thành là [3,2,1,3,2,1,3,2,1].

Ở test case thứ hai, dãy con tăng dần dài nhất của mảng \(b\) là \([1,3,4,6,9]\).