A teacher assigns random numbers to students for a project. Two students can be paired if the product of their assigned numbers is not a perfect square, i.e., it is not the product of some integer multiplied by itself. Each student can participate in at most one pair.

Your task is to find the maximum number of pairs that can be formed after changing at most k numbers to any positive integer.

Example

With arr[4, 12, 20, 5, 20, 5, 451 and k = 1:

4 and 5 can be paired (product 20 is not a perfect square)

12 and 20 can be paired (product 240 is not a perfect square)

Change one 20 to 11, then 11 and 5 can be paired (product 55 is not a perfect square)

This gives us 3 pairs, which is the maximum possible.

Function Description

Complete the function getNon Perfect Pairs in the editor with the following parameter(s):

int arr[n]: original assigned numbers

int k: the number of changes that can be made

Returns

nt: the number of non-perfect pairs

Constraints

1≤ n ≤ 10^5

1 ≤ arr[i] ≤ 10^6

0≤ k ≤n

inpunt

arr[] size n = 6

2

arr = [2, 18, 3, 50, 8, 32]

k = 1

Sample Output

2

Explanation

3 and 2 can be paired together as their product 6 is not a perfect square.

Now, you can change 50 to 1 and pair 1 and 32 together, as their product, 32, is not a perfect square.

input 2

5
1
2
3
4
5
2

ouptout
2

Explanation

1 and 2 can be paired together as product 2 is not a perfect square.

3 and 4 can be paired together as their product, 12, is not a perfect square.