You are given a string 'S' containing only digits. Your task is to find all possible IP addresses that can be obtained from string 'S' in lexicographical order.
A valid IP address consists of exactly four integers, each integer is between 0 and 255 separated by single dots, and cannot have leading zeros except in the case of zero itself.
The following are valid IP addresses:
Following are invalid IP addresses:
0.01.24.255 (as 01 contains one leading zero).
18.312.244.1 (as 312 not lies between 0 and 255).
Input format :
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run.
Then the 'T' test cases follow.
The first line of each test case contains a string 'S'.
Output format :
For each test case, print a single line containing all possible valid IP addresses that can be obtained from 'S' in lexicographical order in a separate line.
Each IP address of a string 'S' is written within quotes("") and separated by comma(,) and space, and all IP addresses of the given string 'S' is written inside square brackets.
1 <= T <= 1000
1 <= |S| <= 15
Where |'S'| denotes the length of string 'S' and 'S' contains only digits from 0 to 9.
Time Limit: 1 sec
You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1 :
Sample Output 1 :
[“126.96.36.199”, “188.8.131.52”, “184.108.40.206”, “220.127.116.11”]
Explanation for sample Input 1:
For the first test case, there is only one possible IP address that is [18.104.22.168]
For the second test case, all possible IP addresses are shown below.
[22.214.171.124], [126.96.36.199], [188.8.131.52], [184.108.40.206]
Sample Input 2 :
Sample Output 2 :
Explanation for sample Input 2:
For the first test case, there is no possible IP address. Therefore then answer is 
For the second test case, there are only 2 possible IP addresses are shown below.