#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stdbool.h>
using namespace std;
#define int long long
int times = 0;
bool flag[2000005] = {0};
int ans[2000005] = {0};
void ss(){
	for(int i = 0 ; i < 1000005 ; i++){
		flag[i] = {0};
		ans[i] = 0;
	}
	times = 0;
}
void shai(int n) {
	ss();
	flag[0] = flag[1] = 1;
	for (int i = 2 ; i <= n ; i++) {
		if (flag[i] == 0) {
			ans[times++] = i;
			for (int j = i + i ; j <= n ; j += i) {
				flag[j] = 1;
			}
		}
	}
}
signed main() {
	int t;
	cin >> t;
	while (t--) {
		int cnt = 0;
		int a;
		cin >> a;
		shai(a);
		for (int i = 0 ; i < times-1 ; i++) {
			if (ans[i + 1] - ans[i] == 1 || ans[i + 1] - ans[i] == 2) {
				cnt++;
			}
		}
		cout << cnt << '\n';
	}
	return 0;
}