Phone List

Interview

Time limit1sMemory limit256 MB

Summary
Given a list of distinct phone numbers, decide whether any number is a prefix of another.
Level

Medium4 of 10

Topics
Trie, String, Sorting
Solved
No attempts yet

Problem

You are given a list of phone numbers. Write a program that determines whether the list is consistent.

A list is consistent if no phone number is a prefix of another phone number.

For example, consider the following list of phone numbers:

  • Emergency: 911
  • Sanggeun: 97 625 999
  • Seonyeong: 91 12 54 26

In this case it is impossible to call Seonyeong. The moment you dial the first three digits 911 of Seonyeong's number, you are connected to the emergency line. Therefore this list is not consistent.

Input

The first line contains the number of test cases tt (1≤t≤501 \le t \le 50).

The first line of each test case contains the number of phone numbers nn (1≤n≤100001 \le n \le 10000).

The next nn lines each contain one phone number from the list. Each phone number is at most 10 digits long, and no phone number appears twice in the same list.

Output

For each test case, print YES if the list is consistent, and NO otherwise, each on its own line.

Examples1

  1. Example 1

    Input
    2
    3
    911
    97625999
    91125426
    5
    113
    12340
    123440
    12345
    98346
    
    Expected output
    NO
    YES