● B là dãy con của A, tức là có thể thu được B bằng cách xóa đi một số phần tử của A (theo định nghĩa này, A cũng là dãy con của A , dãy rỗng cũng là dãy con của A );

● B là một dãy tăng, tức là phần tử đứng sau phải lớn hơn phần tử đứng trước (theo định nghĩa này, dãy gồm không hoặc một phần tử luôn là dãy tăng);

● Hai phần tử liên tiếp của B phải nguyên tố cùng nhau. 

Hãy tìm ra dãy con B có độ dài lớn nhất thỏa mãn các yêu cầu trên.

● Dòng đầu tiên chứa số nguyên dương N (1 ≤ N ≤ 10⁵ );

● N dòng tiếp theo, dòng thứ i chứa số nguyên a_i (1 ≤ a_i ≤ 10¹⁸ ).

● In ra độ dài lớn nhất của dãy con B .

● Subtask 1 (20% số điểm): 1 ≤ N ≤ 20, 1 ≤ a_i ≤ 10⁹ ;

● Subtask 2 (40% số điểm): 1 ≤ N ≤ 5000, 1 ≤ a_i ≤ 10⁹ ;

● Subtask 3 (40% số điểm): không có ràng buộc gì thêm.