// Author: Grzegorz Herman
// O(n^2), quickly checks if answer is 0, if not, iterates like slow1.
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

struct point
{
    int x, y;
    
    friend point operator-(point p, point q)
    {
        point r;
        r.x = p.x - q.x;
        r.y = p.y - q.y;
        return r;
    }

    friend long long operator*(point p, point q)
    {
        return 1LL*p.x*q.y - 1LL*p.y*q.x;
    }
};

void build(vector<vector<point>> & T, int i, int l, int r, vector<point> const & P)
{
    if (l >= r)
        return;
    auto & H = T[i];
    for (int j=l; j<=r; ++j)
    {
        while (H.size() > 1 && (P[j]-H[H.size()-2]) * (H[H.size()-1]-H[H.size()-2]) <= 0)
            H.pop_back();
        H.push_back(P[j]);
    }
    if (r-l > 1)
    {
        build(T, 2*i+0, l, (l+r)/2, P);
        build(T, 2*i+1, (l+r)/2, r, P);
    }
}

bool cuts(point p, point q, vector<point> const & r)
{
    int lo = 0, hi = r.size() - 2;
    while (lo < hi)
    {
        int me = (lo + hi) / 2;
        if ((r[me]-p)*(q-p) < (r[me+1]-p)*(q-p))
            hi = me;
        else
            lo = me+1;
    }
    return ((r[lo]-p)*(q-p) < 0) || ((r[lo+1]-p)*(q-p) < 0);
}

bool lookup(vector<vector<point>> & T, int i, int l, int r, point p, point q, int b, int e, int & w)
{
    if (e <= l || r <= b)
        return false;
    if (b <= l && r <= e)
    {
        if (!cuts(p, q, T[i]))
            return false;
        if (r-l == 1)
        {
            w = l;
            return true;
        }
    }
    return lookup(T, 2*i+0, l, (l+r)/2, p, q, b, e, w) || lookup(T, 2*i+1, (l+r)/2, r, p, q, b, e, w);
}

void testcase()
{
    int n;
    cin >> n;
    vector<point> P(n);
    for (auto & p : P)
        cin >> p.x >> p.y;
    vector<vector<point>> T(4*n);
    build(T, 1, 0, n-1, P);
    for (int i=0; i<n-2; ++i)
        if ((P[i+2]-P[i])*(P[i+1]-P[i]) < 0)
            cout << i+2 << ' ';
        else
        {
            int w = -1;
            lookup(T, 1, 0, n-1, P[i], P[i+1], i+2, n-1, w);
            if (w != -1) {
                int j = i+2;
                while (j<n && ((P[j]-P[i]) * (P[i+1]-P[i]) >= 0))
                    ++j;
                cout << (j<n ? j : 0) << ' ';
            } else cout << 0 << ' ';
        }
    cout << "0" << endl;
}

int main()
{
    int z;
    for (cin >> z; z; --z)
        testcase();
    return 0;
}