- All Contests
- ProjectEuler+
- Project Euler #122: Efficient exponentiation

# Project Euler #122: Efficient exponentiation

# 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`

.