Æ, ø og å i header ved post

Hejsa,

Jeg har en form, hvori du kan søge efter noget i databasen. Det kører så igennem en side, hvor jeg redirecter videre til resultatsiden. Problemet er bare at æ, ø og å bliver til mærkelige tal - hvilket jeg overhovedet ikke kan bruge til noget.

Kode:

<?php
    if(isset($_POST['searchstring'])){
        include ("connect.php");
        $queried = mysqli_real_escape_string($con,$_POST['searchstring']);
       
        $queried = trim($queried);
       
        $patterns = array("/\s+/", "/\s([?.!])/");
        $replacer = array("+","$1");
       
        $queried = preg_replace( $patterns, $replacer, $queried );
        echo $queried;
        header("Location: index.php?page=search&q=".$queried."");
    }
    else {
        header('Location: index.php');
    }
?>

Søger man efter f.eks: æggekage med æbler, så vil resultatsiden være:

index.php?page=search&q=%E6ggekage+med+%E6bler