TreeMap не правильно сортирует

TreeMap не правильно сортирует

import java.util.*;
public class PhonBook {
public static void setMap(String str1, String str2, Map<String, Set> map) {
    if (!map.containsKey(str1)) {
        Set<String> set = new TreeSet<>();
        set.add(str2);
        map.put(str1, set);
    } else {
        Set<String> set = map.get(str1);
        set.add(str2);
        map.put(str1, set);
    }
}
public static void main(String[] args) {
    Map<String, Set> map = new TreeMap<>();
    String str1 = "";
    int k = 0;
    Scanner sc = new Scanner(System.in);
    while (k < 15) {
        if (k % 2 == 0) {
            str1 = sc.nextLine();
        } else {
            String str2 = sc.nextLine();
            if (str2.length() > 6) {
                str2 = str2.replace("(", "");
                str2 = str2.replace(")", "");
                str2 = str2.replace("-", "");
                if ((str2.length() == 12) || (str2.length() == 11) || (str2.length() == 7)) {
                    if (str2.substring(0, 1).equals("8")) {
                        str2 = str2.substring(1);
                        str2 = "+7" + str2;
                    } else if (str2.length() == 7){
                        str2 = "+7495" + str2;
                    }
                    setMap(str1, str2, map);
                }
            }
        }
        k++;
    }
    for (Map.Entry entry: map.entrySet()) {
        System.out.println(entry.getKey());
        Set<String> set = (Set<String>) entry.getValue();
        for (String entrySet: set) {
            System.out.print(entrySet + " ");
        }
        System.out.println();
    }
}
}

Подаю на вход

a1
123456-7
a1
12-(34)-56-7
A1
+7-(888)-50-05-500
джигурда
6666667
Джигурда
8-800-555-35-35
джигурда
8459-666-(666)-7
джигурда
+7(888)-1-2-3-4-5-6-7

Получаю на выходе

A1
+78885005500 
a1
+74951234567 
Джигурда
+78005553535 
джигурда
+74596666667 +74956666667 +78881234567 

А должен бы был получить

A1
+78885005500 
Джигурда
+78005553535 
a1
+74951234567 
джигурда
+74596666667 +74956666667 +78881234567