Sum of Primes
Дизайн и Анализ на Алгоритми, 2011
Time Limit: 1.2s, Memory Limit: 128MiB
Ели имаше гости от чужбина. За да покаже прелестите на България, тя реши да ги разведе надлъжд и нашир от Шумен (Noiseville) до Ямбол (Eatalot), от Котел (Steam Boiler) до Дупница (Assville), от Лютиброд (Hot Chili Ford) до Безмер (Unlimited Village). За да успее да стори това в краткия период на тяхната визита, тя трябваше да намери най-късите пътища между всеки два града. И ги намери. Затова няма да ви занимава с това.

Вместо това ще ви пита каква е сумата на простите числа в даден интервал. Едно естествено число се нарича просто ако има точно два различни делителя – едно и самото то.
Вход
На първия ред на стандартния вход ще бъде зададен броят интервали N, за които ще пита Ели. На всеки от следващите N реда ще има по две цели числа Li и Ri, указващи интервал от Li до Ri, включително, от който момичето се интересува.
Изход
За всеки от интервалите на отделен ред на стандартния изход изпечатайте сумата на простите числа, попадащи в него.
Ограничения
  • 1 ≤ N ≤ 100
  • 1 ≤ LiRi ≤ 10,000,000
Примерен Вход Примерен Изход
3 1 10 42 666 1337 424243 17 36650 7226035576
В първия интервал простите числа са {2, 3, 5, 7}, чиято сума е 17.
Мрън!