D. Max Co Matches
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are going to host an Age of Empires tournament, and you want it to be perfect.

There are $$$n$$$ players participating, you let your friends organize the seating of the players and now on the $$$i$$$-th seat from the left sits a player with a rating $$$a_i$$$.

After you thought everything was going perfect, it turns out that you only had cables with length $$$k$$$ that means player $$$i$$$ can play with player $$$j$$$ iff ($$$|j - i| \leq k$$$), and if that wasn't bad enough all the players are elitist, so the player $$$i$$$ will play with player $$$j$$$ iff $$$a_i$$$ and $$$a_j$$$ are coprime.

Given the seating of the $$$n$$$ players and length of the cable $$$k$$$ what is the maximum number of matches can you set up. Note that each player can only participate in one match.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ $$$(1 \leq n \leq 10^5; 1 \leq k \leq 8)$$$ – the number of players and the length of the cable.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$ – the ratings of the players.

Output

Print a single integer, the answer to the problem.

Examples
Input
3 2
1 2 3
Output
1
Input
4 2
1 2 3 5
Output
2
Input
5 1
6 2 2 4 5
Output
1
Note

In the first sample, you could set up the following match: $$$(1, 3)$$$.

In the second sample, this is one of the ways you could set up the matches: $$$(2, 5), (1, 3)$$$.