Xét bài toán sau: Cho dãy số gồm \(N\) số nguyên dương, hãy cho biết bội số chung nhỏ nhất (LCM) của toàn dãy nếu ta biến đổi một phần tử của nó về giá trị \(1\).

Nhận thấy đề bài chưa đủ khó, Đức quyết định nâng cấp nó lên:

• Các phần tử trong dãy thay vì được cho trực tiếp sẽ được biểu diễn dưới dạng tích của các thừa số nguyên tố. Cụ thể, phần tử thứ \(i\) sẽ gồm \(m_i\) thừa số nguyên tố \(p_1\), \(p_2\),..., \(p_{m_i}\), với số mũ tương ứng là \(e_{1,i}\), \(e_{2,i}\),..., \(e_{m_i,i}\). Nói cách khác, giá trị của nó sẽ bằng \(p_1^{e_1,i}\times p_2^{e_2,i}\times p_3^{e_3,i}\times ... \times p_{m_i}^{e_{m_i},i}\).
• Ta lần lượt thử biến đổi từng phần tử thứ \(1\), \(2\), \(3\),..., \(N\) về giá trị \(1\), và tính xem có tổng số bao nhiêu giá trị LCM khác nhau có thể thu được (mỗi lần thử chỉ biến đổi đúng một phần tử).

Input

• Dòng đầu chứa số nguyên dương \(N\) \(\left(1\le N\le 2\times 10^5\right)\).
• Nhóm dòng thứ \(i\) trong \(N\) nhóm dòng tiếp theo bắt đầu bởi một dòng chứa số nguyên dương \(m_i\). Theo sau là \(m_i\) dòng, dòng thứ \(j\) chứa thừa số nguyên tố \(p_j\) và số mũ \(e_j\) \(\left(1\le p_j, e_j\le 10^9\right)\).
• Dữ liệu đảm bảo tổng tất cả giá trị \(m_i\) không vượt quá \(2\times 10^5\). Đồng thời, tất cả các giá trị \(p\) đều là số nguyên tố.

Output

• In ra một số nguyên là số lượng giá trị LCM khác nhau ta có thể thu được sau \(N\) lần thử nghiệm.

Ví dụ

Sample input 01

4
1
3 2
2
2 2
5 1
1
5 1
2
2 1
3 1

Sample output 01

3

Giải thích

• Các phần tử ban đầu của dãy là: \(3^2=9\), \(2^2\times 5^1=20\), \(5^1=5\), \(2^1\times 3^1=6\).
• Nếu gán phần tử đầu tiên bằng \(1\), ta được dãy: \([1, 20, 5, 6]\). Dãy này có LCM bằng \(60\).
• Nếu gán phần tử thứ nhì bằng \(1\), ta được dãy: \([9,1,5,6]\). Dãy này có LCM bằng \(90\).
• Nếu gán phần tử thứ ba bằng \(1\), ta được dãy: \([9, 20, 1, 6]\). Dãy này có LCM bằng \(180\).
• Nếu gán phần tử cuối cùng bằng \(1\), ta được dãy: \([9, 20, 5, 1]\). Dãy này có LCM bằng \(180\).
• Vậy có tổng cộng \(03\) giá trị LCM khác nhau là \(60\), \(90\), và \(180\).