#include<iostream>
#include<queue>
using namespace std;
void solve() {
	priority_queue<int>q1; priority_queue<int,vector<int>,greater<int> >q2; int cnt=0;
	while(true) {
		int n; cin>>n;
		if(!n) return;
		if(!(~n)) {
			cout<<q1.top()<<'\n',q1.pop(),cnt--;
			while(q1.size()<(cnt+1)/2) q1.push(q2.top()),q2.pop();
			while(q1.size()>(cnt+1)/2) q2.push(q1.top()),q1.pop();
		}
		else {
			cnt++,q1.push(n);
			while(q1.size()<(cnt+1)/2) q1.push(q2.top()),q2.pop();
			while(q1.size()>(cnt+1)/2) q2.push(q1.top()),q1.pop();
		}
	}
}
int main() {
	ios::sync_with_stdio(false),cin.tie(nullptr);
	int t; cin>>t;
	while(t--) solve();
	return 0;
}