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.
The first line of input contains , the number of test cases.
Each test case consists of a single line containing a single integer, .
Input file #1: .
Input file #2: .
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.