#include <iostream>
#include <vector>

using namespace std;

int gcd(int a, int b) {
  if (b == 0)
    return a;
  return gcd(b, a % b);
}

bool is_independent(vector<int>& subset) {
  int n = subset.size();
  int g = subset[0];
  for (int i = 1; i < n; i++)
    g = gcd(g, subset[i]);
  return (g == 1);
}

void backtrack(vector<int>& nums, int start, vector<int>& subset, int& count) {
  if (start == nums.size()) {
    if (is_independent(subset))
      count++;
    return;
  }
  backtrack(nums, start + 1, subset, count);
  subset.push_back(nums[start]);
  backtrack(nums, start + 1, subset, count);
  subset.pop_back();
}

int independent_subsets(vector<int>& nums) {
  int count = 0;
  vector<int> subset;
  backtrack(nums, 0, subset, count);
  return count;
}

int main() {
  vector<int> nums = {1, 2, 3, 4, 5};
  cout << independent_subsets(nums) << endl;
  return 0;
}