Sum Over Subsets

You are given a multiset S. Over all pairs of subsets A and B, such that:

• B ⊂ A;
• |B| = |A| - 1;
• greatest common divisor of all elements in A is equal to one;

find the sum of ∑{x ∈ A}{x} ⋅ ∑{x ∈ B}{x}, modulo 998 244 353.

Input

The first line contains one integer m (1 ≤ m ≤ 10^5): the number of different values in the multiset S.

Each of the next m lines contains two integers a_i, freq_i (1 ≤ a_i ≤ 10^5, 1 ≤ freq_i ≤ 10^9). Element a_i appears in the multiset S freq_i times. All a_i are different.

Output

Print the required sum, modulo 998 244 353.

Examples

Input

2 1 1 2 1

Output

9

Input

4 1 1 2 1 3 1 6 1

Output

1207

Input

1 1 5

Output

560

Note

A multiset is a set where elements are allowed to coincide. |X| is the cardinality of a set X, the number of elements in it.

A ⊂ B: Set A is a subset of a set B.

In the first example B={1}, A={1,2} and B={2}, A={1, 2} have a product equal to 1⋅3 + 2⋅3=9. Other pairs of A and B don't satisfy the given constraints.

inputFormat

Input

The first line contains one integer m (1 ≤ m ≤ 10^5): the number of different values in the multiset S.

Each of the next m lines contains two integers a_i, freq_i (1 ≤ a_i ≤ 10^5, 1 ≤ freq_i ≤ 10^9). Element a_i appears in the multiset S freq_i times. All a_i are different.

outputFormat

Output

Print the required sum, modulo 998 244 353.

Examples

Input

2 1 1 2 1

Output

9

Input

4 1 1 2 1 3 1 6 1

Output

1207

Input

1 1 5

Output

560

Note

A multiset is a set where elements are allowed to coincide. |X| is the cardinality of a set X, the number of elements in it.

A ⊂ B: Set A is a subset of a set B.

In the first example B={1}, A={1,2} and B={2}, A={1, 2} have a product equal to 1⋅3 + 2⋅3=9. Other pairs of A and B don't satisfy the given constraints.

样例

1
1 5

560

</p>