Project Euler #122: Efficient exponentiation

_{This problem is a programming version of Problem 122 from projecteuler.net}

The most naive way of computing requires fourteen multiplications:

But using a "binary" method you can compute it in six multiplications:

However it is yet possible to compute it in only five multiplications:

We shall define to be the minimum number of multiplications to compute . For example .

For a given , compute , and also output the sequence of multiplications needed to compute . See the sample output for more details.

Input Format

The first line of input contains , the number of test cases.

Each test case consists of a single line containing a single integer, .

Constraints

Input file #1: .
Input file #2: .

Output Format

For each test case, first output in a single line. Then output lines, each of the form n^a * n^b = n^c, where a, b and c are natural numbers. You may also output n instead of n^1. Use the * (asterisk/star) symbol, not the letter x or something else.

The sequence of multiplications must be valid. Any valid sequence will be accepted.

Sample Input

2
2
15

Sample Output

1
n^1 * n^1 = n^2
5
n * n = n^2
n^2 * n = n^3
n^3 * n^3 = n^6
n^6 * n^6 = n^12
n^12 * n^3 = n^15

Explanation

The second case, , is the example given in the problem statement.

The sample output illustrates that you can use n instead of n^1.