Fermierul Amooot merge la magazinul de furaje pentru a achiziționa amestecuri de iarbă pentru pășunatul vacilor sale. Vânzătorul Popică, viclean de fel, îi prezintă un șir V de N oferte; însă, pentru ca Amooot să poată achiziționa hrana, acesta va trebui neapărat să selecteze o subsecvență canonică de oferte!

Spunem că o subsecvență A[i], A[i+1], … , A[j] , 1 ≤ i ≤ j ≤ N este canonică dacă A[k] % A[i] = 0, pentru orice k, i ≤ k ≤ j. De exemplu, în șirul (3, 4, 2, 10, 4, 12, 3), subsecvențe canonice sunt (2, 10) sau (2, 10, 4, 12), dar nu și subsecvența (10, 4, 12).

Cerința

Văzând condițiile impuse de Popică, Amooot își pune două întrebări:

1. Care este cea mai lungă subsecvență canonică din V?
2. Câte subsecvențe canonice există în V?

Date de intrare

Fișierul de intrare canonic.in conține pe prima linie numărul C, numărul cerinței de rezolvat.

Pe a doua linie a fișierului de intrare se găsește numărul N, reprezentând numărul elementelor șirului de oferte.

Pe a treia linie a fișierului de intrare se vor găsi N numere naturale, care reprezintă șirul de oferte 𝑉 . Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire canonic.out va conține pe prima linie răspunsul la cerința din test.

Restricții și precizări

• C ∈ {1, 2}
• 1 ≤ N ≤ 500 000
• 1 ≤ V[i] ≤ 1012, pentru orice 1 ≤ i ≤ N
• Atenție la limita de memorie!

Subtaskuri

1. C = 1, N ≤ 500
2. C = 1, N ≤ 2 000
3. C = 1, N ≤ 100 000, V[i] ≤ 1 000, pentru orice 1 ≤ i ≤ N
4. C = 1, Fără restricții suplimentare.
5. C = 2, V[i] = 1, pentru orice 1 ≤ i ≤ N
6. C = 2, N ≤ 500
7. C = 2, N ≤ 2 000
8. C = 2, N ≤ 100 000, V[i] ≤ 1 000, pentru orice 1 ≤ i ≤ N
9. C = 2, Fără restricții suplimentare.

Exemplul 1

canonic.in

1
7
3 4 2 10 4 12 3

canonic.out

4

Explicație

Subsecvența canonică de lungime maximă din șir este (2, 10, 4, 12). Așadar, lungimea maximă este 4.

Exemplul 2

canonic.in

2
7
3 4 2 10 4 12 3

canonic.out

11

Explicație

Subsecvențele canonice din șir sunt:

1. (3)
2. (4)
3. (2)
4. (2, 10)
5. (2, 10, 4)
6. (2, 10, 4, 12)
7. (10)
8. (4)
9. (4, 12)
10. (12)
11. (3)