Để khuyến khích các bạn trẻ nghiên cứu và chế tạo robot, Thành Đoàn Hà Nội đã tổ chức một hoạt động có tên "ROBOT tặng quà" dành cho các bạn thí sinh của kỳ thi Tin học trẻ. Hoạt động đó diễn ra như sau:

Trên trục số có một robot đặt tại điểm ~0~ và ~n~ bạn đánh số từ ~1~ tới ~n~, bạn thứ ~i~ đứng tại điểm ~a_i~ trên trục số (có thể có nhiều bạn đứng cùng một vị trí). Người chơi chính được lựa chọn một số nguyên ~d~ (~d > 1~) và thiết đặt bước nhảy của robot là ~d~. Khi đó, từ một vị trí, robot có thể nhảy tiến hoặc nhảy lùi một khoảng cách đúng bằng ~d~ trên trục số, tức là nếu robot đang ở vị trí ~x~, robot chỉ có thể nhảy sang một trong hai vị trí ~x + d~ hoặc ~x - d~. Một bạn sẽ được robot tặng quà nếu tồn tại cách di chuyển robot nhảy từ điểm ~0~ tới vị trí bạn đó sau một số hữu hạn lần nhảy.

Với mong muốn có nhiều bạn được robot tặng quà, em hãy giúp người chơi chính chọn tham số nguyên ~d > 1~ để có nhiều bạn được robot tặng quà nhất, cho biết số bạn được robot tặng quà.

Dữ liệu: Vào từ thiết bị vào chuẩn

• Dòng đầu chứa số nguyên dương ~T \le 10^5~ là số bộ dữ liệu
• ~T~ nhóm dòng tiếp theo, mỗi nhóm gồm hai dòng mô tả một bộ dữ liệu:
  • Dòng ~1~ chứa số nguyên dương ~n \le 10^6~
  • Dòng ~2~ chứa ~n~ số nguyên ~a_1, a_2, ... , a_n~ cách nhau bởi dấu cách (~|a_i| \le 10^6~ với ~1 \le i \le n~)
    Tổng các giá trị ~n~ trong các bộ dữ liệu vào không vượt quá ~10^6~.

Kết quả: Ghi ra thiết bị ra chuẩn
Với mỗi bộ dữ liệu, ghi ra một số nguyên duy nhất trên một dòng là số bạn được robot tặng quà theo phương án tìm được.

Ví dụ:

Ràng buộc:

• Có 20% số lượng test ứng với 20% số điểm có ~n \le 100; |a_i| \le 100~ với ~1 \le i \le n~;
• Có 30% số lượng test khác ứng với 30% số điểm có ~n \le 2000; |a_i| \le 2000~ với ~1 \le i \le n~;
• Có 50% số lượng test còn lại ứng với 50% số điểm không có ràng buộc bổ sung.