github.com/captn3m0/codechef.git

---
category_name: medium
problem_code: KOL1508
problem_name: Antichains
languages_supported:
    - C
    - CPP14
    - JAVA
max_timelimit: '1.5'
source_sizelimit: '50000'
problem_author: piyushkumar
problem_tester: null
date_added: 10-12-2015
tags:
    - acm15kol
    - combinatorics
    - piyushkumar
    - sperners
    - theorem
editorial_url: 'http://discuss.codechef.com/problems/KOL1508'
time:
    view_start_date: 1451123700
    submit_start_date: 1451123700
    visible_start_date: 1451123700
    end_date: 1735669800
    current: 1493557921
layout: problem
---
All submissions for this problem are available.Given an integer **N**, let **FN** be the set of factors of **N**. e.g., **F6** = {1,2,3,6}.

The radical of an integer **N**, denoted by **rad(N)**, is defined as the product of the distinct prime factors of **N**. e.g., **rad(12)** = 2 \* 3 = 6.

Define an **antichain** of a set **S** of integers to be a subset of **S** such that for any two elements x and y in the antichain, rad(x) and rad(y) do not divide each other. e.g., antichains in **F6** are {}, {1}, {2}, {3}, {6} and {2,3}.

Given **N**, find the size of the largest antichain of **FN**, and the number of antichains of FN of that size. Since the answers can be large, print both of them modulo **(109+7)**.

e.g., if **N** = 6, the largest antichain is of size 2, and there is only 1 antichain of that size.

Since **N** can be large, the input is the prime factorization of **N**. The input has two arrays of size **M**: **base** and **power**, and **N = base1power1 \* base2power2 \* … \* baseMpowerM**.

### Input

- The first line contains **T**, the number of test cases. Description of the **T** test cases follows.
- Each test case starts with a single integer **M**.
- The next **M** lines each contain 2 integers separated by a space. The **i**th line contains **basei** and **power\_i.**

### Output

- For each test case, output one line containing two space-separated integers, respectively the size of the largest antichain modulo (109+7) and the number of antichains of that size, again modulo (109+7).

### Constraints

- 1 ≤ T ≤ 10
- 1 ≤ M ≤ 105
- 2 ≤ basei ≤ 109
- 1 ≤ power\_i ≤ 109
- basei is a prime number for all 1 ≤ i ≤ M
- For any 1 ≤ i ≠ j ≤ M, basei ≠ basej



**NOTE: Input files can be large. Please use fast input methods (e.g. scanf in C/C++, BufferedReader in Java)**/>

### Example

<pre><b>Input:</b>
2
2
2 1
3 1
2
2 2
3 1

<b>Output:</b>
2 1
2 2
</pre>### Explanation

**Example case 1.** The largest antichain size is 2, and there is only one of it {2,3}

**Example case 2.** The largest antichain size is 2, and there are two of those: {2,3} and {4,3}