P5762 - On Iteration of One Well-Known Function

内存限制：256 MB 时间限制：2 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：3 通过：1

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.

Input

The first line contains integer m (1≤m≤10⁵) − 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⁶;1≤a_i≤10¹⁷) − another prime divisor of number n and its power in the canonical representation. The sum of all a_i doesn't exceed 10¹⁷. Prime divisors in the input follow in the strictly increasing order.
The last line contains integer k (1≤k≤10¹⁸).

Output

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.

Examples

Input

1
7 1
1

Output

2
2 1
3 1

Input

1
7 1
2

Output

1
2 1

Input

1
2 100000000000000000
10000000000000000

Output

1
2 90000000000000000

Note

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.

396E

5762: On Iteration of One Well-Known Function

题目描述

输入样例复制

输出样例复制

分类标签

5762: On Iteration of One Well-Known Function

题目描述

输入样例 复制

输出样例 复制

分类标签

输入样例复制

输出样例复制