/************************************************
Algorithmen und Problemloesungen mit C++,
http://www.algorithmen-und-problemloesungen.de
Copyright @2007 by Doina Logofatu
************************************************/

#include <fstream>
#include <vector>

unsigned mod_inverse(unsigned a, unsigned m){
  unsigned i;
  for(i=0; i<m; i++)
    if(1==(a*i)%m) return i;
  return 0;
}

int main(){
  std::vector<unsigned> a, m;
  unsigned i, j, M1, M=1, X=0;
  std::ifstream in("baerchen.in");
  std::ofstream out("baerchen.out");
  while(in && in>>i>>j){
    a.push_back(i); m.push_back(j);
    M *= j;
  }
  for(i=0; i<a.size(); i++){
    M1 = M/m[i];
    X += a[i]*M1*mod_inverse(M1, m[i]);
  }
  out << X%M;
  return 0;
}