Valid IP Address Generation

You are given a string containing only digits. Your task is to insert three dots into the string to form a valid IPv4 address. A valid IPv4 address consists of four integers (each between \(0\) and \(255\)) separated by dots. Note that an integer cannot have leading zeros (except the number 0 itself). Formally, a segment is valid if it satisfies \(0 \leq \text{segment} \leq 255\) and if it has more than one digit, it cannot start with a '0'.

If there is no possible valid IP address from the input string, print exactly "No valid IP addresses". If there are multiple valid IP addresses, output them in lexicographical order (i.e. sorted as strings) with each address on a separate line.

Input Format: The first line contains an integer \(T\) indicating the number of test cases. Each of the following \(T\) lines contains a non-empty string of digits.

Output Format: For each test case, output the valid IP addresses, each on a new line. If a test case has no valid IP addresses, output "No valid IP addresses" on a single line.

inputFormat

The first line of input contains an integer \(T\) (\(1 \le T \le 100\)) representing the number of test cases. Each test case consists of one line containing a string \(S\) of digits (with length from 1 to 12).

outputFormat

For each test case, output all valid IP addresses in lexicographical order (sorted as strings), each on a new line. If there is no valid IP address, output "No valid IP addresses".

## sample

2
25525511135
010010

255.255.11.135
255.255.111.35
0.10.0.10
0.100.1.0

</p>