Cho ~N~ (~1≤N≤20~) phương trình bậc nhất có dạng: ~ax+b=0~ (~a≠0~), hai số nguyên ~a~, ~b~ (~|a|,|b|≤10^{12}~) được gọi là hệ số của phương trình, ~x~ là ẩn số.

Yêu cầu: Hãy đếm số lượng phương trình có nghiệm nguyên dương, đồng thời nghiệm đó là số nguyên tố.

Input

• Dòng thứ nhất chứa số nguyên dương ~N~.
• ~N~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~a~ và ~b~, cách nhau một khoảng trắng

Output

• Xuất ra màn hình một số nguyên là số lượng phương trình có nghiệm thỏa mãn yêu cầu bài toán

Example

Input

3
1 -3
12 -6
-50 -100

Output

1