On Iteration of One Well-Known Function

## 题目描述 给定$n$和$k$，求出$\varphi(\varphi(...\varphi(n)...))$(k层嵌套)的值。 由于$n$的值很大，所以$n$将会由给定将$n$质因数分解后的质因数以及其次数的方式给出。 ## 输入格式 第一行一个正整数$m(1 \leq m \leq 10^5)$，表示$n$的不同的质因数个数。 接下来$m$行，每行两个正整数$p_i(1 \leq p_i \leq 10^6)$和$a_i(1 \leq a_i \leq 10^{17})$，分别表示$n$的一个质因数以及其指数。保证质因数按照升序给出。 最后一行一个正整数$k(1 \leq k \leq 10^{17})$，含义如题目描述所述。 ## 输出格式 输出时请按照升序输出答案所包含的质因数以及其次数。 第一行输出其质因数个数$w$。 接下来$w$行，每行两个正整数$q_i$和$b_i(b_i >= 1)$表示答案的一个质因子是$q_i$，且将答案质因数分解后包含$b_i$个$q_i$

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<=m<=10^{5} $ ) — the number of distinct prime divisors in the canonical representaion of $ n $ . Each of the next $ m $ lines contains a pair of space-separated integers $ p_{i},a_{i} $ ( $ 2<=p_{i}<=10^{6}; 1<=a_{i}<=10^{17} $ ) — another prime divisor of number $ n $ and its power in the canonical representation. The sum of all $ a_{i} $ doesn't exceed $ 10^{17} $ . Prime divisors in the input follow in the strictly increasing order. The last line contains integer $ k $ ( $ 1<=k<=10^{18} $ ).

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.

1
7 1
1

2
2 1
3 1

1
7 1
2

1
2 1

1
2 100000000000000000
10000000000000000

1
2 90000000000000000

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.