Here's how I'd rewrite your program:

#!/usr/bin/perl

use warnings;
use strict;
use diagnostics;

my $found_query = 0;

while(<>) {
        if($found_query) {
                m/^>([^\s]+)/ and do {
                        print "$1\n";
                        $found_query = 0;
                }
        } else {
                m/^Query=\s([^\s]+)/ and do {
                        print "$1\t";
                        $found_query = 1;
                }
        }
}
[download]

Does this do what you want?