TheJobOverflow | Magic Number

Magic Number :

Author

Akshay Sharma

Difficulty Level : Easy

Submissions : 94

Asked In : Tech-Mahindra

Marks :100

: 2 | : 0

Amit is fond of Magic number. one day he is planning a trip from City A to B where there is exactly N rest point between both the cities and every rest point have an ID(Not necessary unique), Amit stop only those rest point whose ID(Hotel ID) is a magic number. if there is no rest point whose ID is a magic number then Amit didn't stop at any such points and reached city B directly. Now before planning the trip Amit wants to know In how many rest points he can stop his car and have some rest.

Note: According to Amit magic number is a number which is a perfect Square of any number eg:0,1,4,9....N

Input

The first line of the test case contains a single integer N ( $0 \le N, M \le 10^6$ ) — the number of rest points from city A to B.

The second line of each test case contains N integers $a_i$ , $a_{i+1}$ ..... $a_{n-1}$ ( $0 \le a_i \le 10^6$ ) — the ID of each rest point or hotel number .

Output

For each test case, print one integer on a single line — the count of total numbers magic number that Amit has.

Examples

Input

5
25 77 54 81 48

Output

Input

10
0 3 5 10 15 16 18 19 200 625

Output

You need to login to view your submissions.

You need to login to view all submissions.

Language

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
  using namespace std;
  int main() {
    cout << "Hello World";
    return 0;
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Result : Executed

Result : Accepted

Test Cases :