Count numbers with atleast one common factor, excluding one (updated)
Your algorithm is very far from optimal. In the worst case (if all numbers are equal to N in the input), it does O(N * T) operations, which clearly way too much (not just for python, for any programming language). 

What they're asking to compute is n - phi(n), where phi is the Euler's totient function. Using the fact that the function is multiplicative one can derive a formula phi(n) = n * {product of (1 - 1 / p) over all prime p dividing n. Using this fact, we can compute it efficiently in O(N log log N) time for all 1 &lt;= i &lt;= N using something that looks like the sieve of Eratosthenes. After that, we can answer each query in O(1). 

A C++ implementation is ridiculously concise and easily fits in the time limit:

#include &lt;cstdio&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

int main() {
    const int max_n = 1000 * 1000;
    std::vector&lt;int&gt; ans(max_n + 1);
    std::iota(ans.begin(), ans.end(), 0);
    for (int i = 2; i &lt;= max_n; i++)
        if (ans[i] == i)
            for (int j = i; j &lt;= max_n; j += i)
                ans[j] = ans[j] / i * (i - 1);
    int t;
    scanf("%d", &amp;t);
    while (t--) {
        int x;
        scanf("%d", &amp;x);
        printf("%d\n", x - ans[x]);
    }
}


Unfortunately, the same solution in python is too slow. 

def calc_phi(n):
    res = [i for i in range(n + 1)]
    is_prime = [True] * (n + 1)
    for i in range(2, n + 1):
        if is_prime[i]:
            for j in range(2 * i, n, i):
                is_prime[j] = False
                res[j] = res[j] // i * (i - 1)
    return res


def solve():
    max_n = 10 ** 6
    phi = calc_phi(max_n)
    cnt = int(input())
    res = []
    for _ in range(cnt):
        n = int(input())
        res.append(n - phi[n])
    print('\n'.join(map(str, res)))


if __name__ == '__main__':
    solve()


With some optimizations (like more efficient input reading and handling small prime divisors separately), which made the code less readable and nice, I managed to make it complete under 1 second in the worst case on my machine, which is pretty close. It's still too slow for the online judge. So I'm not sure if it's actually solvable in python. That's the main reason why python is rarely used to solve problems with a tight time limit: it's much slower than C++ or Java.