SP178 ROADNET - Road net

A diskette was enclosed to a road map. The diskette contains the table of the shortest ways (distances) between each pair of towns on the map. All the roads are two-way. The location of towns on the map has the following interesting property: _if the length of the shortest way from town A to town B equals the sum of the lengths of the shortest ways from A to C and C to B then town C lies on (certain) shortest way from A to B_. We say that towns A and B are neighbouring towns if there is no town C such that the length of the shortest way from A to B equals the sum of the lengths of the shortest ways from A to C and C to B. Find all the pairs of neighbouring towns.

The number of test cases _t_ is in the first line of input, then _t_ test cases follow separated by an empty line. In the first line of each test case there is an integer _n_, 1

For each test case your program should write all the pairs of the neighbouring towns (i.e. their numbers). There should be one pair in each line. Each pair can appear only once. The numbers in each pair should be given in increasing order. Pairs should be ordered so that if the pair (_a_, _b_) precedes the pair (_c_, _d_) then _a_ < _c_ or (_a_ = _c_ and _b_ < _d_). Consequent test cases should by separated by an empty line.