Pair Sum

Time limit1sMemory limit128 MB

Summary

This is a straightforward simulation task where numbers in each test case are used to enumerate pairs. For each input n, all pairs of distinct natural numbers with sum n are printed in lexicographic order. Because n is at most 12, iterating all possible a and b values directly works. Implemented with simple loops, this problem is a typical warm-up exercise.

Level: Easy1 of 10
Topics: Simulation, Brute force, Implementation
Solved: No attempts yet

Problem

Given a natural number $n$ with $1 \le n \le 12$ , write a program that finds every pair of two distinct natural numbers whose sum is $n$ .

Each pair has the form $(a, b)$ , where the two numbers must be different (for example, $3$ and $3$ is not a valid pair) and the first number must always be smaller than the second one ( $a < b$ ).

Print the pairs in lexicographic order, comparing by the smaller number (the first number) of each pair. For example, $(1, 5)$ comes before $(2, 4)$ .

Input

The first line contains the number of test cases $T$ ( $T < 100$ ). Each of the next $T$ lines contains one natural number $n$ ( $1 \le n \le 12$ ).

Output

For each test case, first print Pairs for n: (where n is the actual value). Then, after a single space, print the pairs whose sum is $n$ in lexicographic order, separated by , (a comma and a space). Each pair is printed as a b, its two numbers separated by a single space. If there is no pair that sums to $n$ , print nothing after Pairs for n:.

Examples1

Example 1

Input

Expected output

Pairs for 2:
Pairs for 3: 1 2
Pairs for 4: 1 3
Pairs for 5: 1 4, 2 3