/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static int n = (int)1e6;
	public static int N = 5;
	public static long[] arr = {1, 36, 9, 4, 6};
	public static long[] smallestPrimeFact = new long[n + 1];
	public static long[] Prefix_Odd_Part = new long[N + 1];
	
	
	public static void spf(){
	for(int i = 2; i <= n; i++){
			smallestPrimeFact[i] = i;
		}
 
		for(int i = 2; i <= Math.sqrt(n); i++){
			if(smallestPrimeFact[i] == i){
				for(int j = i*i; j <= n; j += i){
					if(smallestPrimeFact[j] == j){
						smallestPrimeFact[j] = i; 
					}
				}
			}
		}
}
	
	public static HashMap<Long, Long> function(long vl){
		HashMap<Long, Long> map = new HashMap<>();
		
		while(vl != 1){
			long d = smallestPrimeFact[(int)vl];
			map.put(d, map.getOrDefault(d,0L) + 1);
			vl /= d;
		}
		return map;
	}
	
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Prefix_Odd_Part[0] = 1;
		Long count = 0L;
		
		spf();
		
		HashMap<Long, Long> map = new HashMap<>();
		map.put(1L, 1L);
		for(int i = 0; i < N; i++){
			HashMap<Long, Long> k = function(arr[i]);
			
			long oddPart = 1;
			
			for(Map.Entry<Long, Long> en : k.entrySet()){
				long key = en.getKey();
				long freq = en.getValue();
				
				if(freq % 2 != 0){
					oddPart *= key;
				}
			}
			
			long curr = Prefix_Odd_Part[i] * oddPart;
			
			 k = function(curr);
			 
			 long preOddPart = 1;
			 
			 for(Map.Entry<Long, Long> en : k.entrySet()){
				long key = en.getKey();
				long freq = en.getValue();
				
				if(freq % 2 != 0){
					preOddPart *= key;
				}
			}
			
			Prefix_Odd_Part[i+1] = preOddPart;
			
			count += map.getOrDefault(preOddPart, 0L);
			map.put(preOddPart, map.getOrDefault(preOddPart, 0L) + 1);
		}
		System.out.println(count);
	}
}