CF396E On Iteration of One Well-Known Function

Of course, many of you can calculate $ φ(n) $ — the number of positive integers that are less than or equal to $ n $ , that are coprime with $ n $ . But what if we need to calculate $ φ(φ(...φ(n))) $ , where function $ φ $ is taken $ k $ times and $ n $ is given in the canonical decomposition into prime factors? You are given $ n $ and $ k $ , calculate the value of $ φ(φ(...φ(n))) $ . Print the result in the canonical decomposition into prime factors.

The first line contains integer $ m $ ( $ 1

In the first line, print integer $ w $ — the number of distinct prime divisors of number $ φ(φ(...φ(n))) $ , where function $ φ $ is taken $ k $ times. Each of the next $ w $ lines must contain two space-separated integers $ q_{i},b_{i} $ $ (b_{i}>=1) $ — another prime divisor and its power in the canonical representaion of the result. Numbers $ q_{i} $ must go in the strictly increasing order.

You can read about canonical representation of a positive integer here: http://en.wikipedia.org/wiki/Fundamental\_theorem\_of\_arithmetic. You can read about function $ φ(n) $ here: http://en.wikipedia.org/wiki/Euler's\_totient\_function.