Uesugi Tèo - một coder nổi tiếng trong đội tuyển Tin Ams, đã được gia đình nhà Nakano giàu có thuê làm gia sư Tin học dạy kèm con họ. Lạ thay, những đứa con của gia đình nọ là những người chị em sinh năm học cùng khối với cậu trên trường. Bằng quyết tâm và nhiệt huyết với việc giúp 5 chị em họ vượt qua bài kiểm tra của thầy Tùng, Uesugi đã giao mỗi người một bài toán phù hợp với năng lực của họ, với phần thưởng đi kèm là một chuyến dã ngoại cùng cậu. Sau khi đắn đo suy nghĩ, cậu giao cho Nino Nakano bài toán như sau:

Nino được cho ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ và một số nguyên dương ~K~. Cô được yêu cầu chọn ra một dãy các vị trí ~i_1, i_2, \dots, i_M \ (1 \leq M \leq N)~ trong số ~N~ vị trí ban đầu, sao cho trong những vị trí được chọn, không tồn tại hai vị trí ~i_x, i_y \ (i_x \neq i_y) ~ thỏa mãn ~a_{i_x} \times a_{i_y}~ là một lũy thừa bậc ~K~. Ví dụ, với ~K = 2~ và ~a = \{1, 2, 8, 16, 3, 9\}~, Nino có thể chọn tập ~\{1, 2, 5\}~ hoặc ~\{4\}~, nhưng không thể chọn đồng thời vị trí ~(1, 4)~, hay ~(4, 6)~. Để làm bài toán khó hơn, Uesugi yêu cầu Nino tìm dãy con lớn nhất thỏa mãn điều kiện trên. Nếu không tồn tại đoạn thỏa mãn, Nino cần trả về -1.

Nino không muốn trông cậy vào sự giúp đỡ của Uesugi, nên bạn được yêu cầu giải bài toán này nhanh nhất có thể để không làm phật lòng Uesugi cũng như những người chị em của cô.

Input

• Dòng đầu tiên nhập vào hai số nguyên dương ~N, K \ (1 \leq N \leq 2 \times 10^5, \ 2 \leq K \leq 5)~.
• Dòng tiếp theo nhập vào ~N~ số nguyên dương ~a_1, a_2, \dots, a_N \ (1 \leq a_i \leq 2 \times 10^6)~ được ngăn bởi dấu cách.

Output

• In ra một số nguyên duy nhất là kết quả của bài toán hoặc -1 nếu không tồn tại dãy thỏa mãn.

Scoring

• Subtask 1 ~(7p)~: ~N \leq 14~.
• Subtask 2 ~(13p)~: ~N \leq 20~.
• Subtask 3 ~(11p)~: ~K = 2, \ N \leq 2000~.
• Subtask 4 ~(16p)~: ~N \leq 2000~.
• Subtask 5 ~(22p)~: ~K = 2~.
• Subtask 6 ~(31p)~: Không có ràng buộc gì thêm.

Sample Input 1

6 2
1 2 8 16 3 9

Sample Ouput 1

3

Notes

• Chọn các số ~\{1, 3, 5\}~.