ნახევრად მარტივი რიცხვები

დროის ლიმიტი: 2 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout


ნახევრად მარტივი რიცხვები არიან რიცხვები რომლებიც იყოფიან მხოლოდ ერთ მარტივ რიცხვზე. უნდა დაწეროთ პროგრამა, რომელიც დაადგენს, თუ რამდენი ნახევრად მარტივი რიცხვია მოცემულ დიაპაზონში.

შემავალი  მონაცემები: პირველ სტრიქონში ერთი მთელი რიცხვი, n (n ≤ 100) რომელიც განსაზღვრავს რამდენი წყვილი უნდა შემოვიდეს. თითოეული წყვილი შეიცავს ორ მთელ რიცხვს, რომელშიც მეორე რიცხვი დიდია პირველზე (0 <პირველი რიცხვი ≤ მეორე რიცხვი ≤ 1012).

გამომავალი მონაცემები: გამოდის მონაცემების თითო ხაზი, რომელიც გვიჩვენებს თუ რამდენი ნახევრად მარტივი რიცხვია მოცემულ დიაპაზონში.




მაგალითები

შესატანი მონაცემები
3 1 10 1 20 1 5 დაკოპირება
გამოსატანი მონაცემები
3 4 1 დაკოპირება