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.