#include <iostream>
#include <map>
#include <vector>
using namespace std;
map<int,int> m;
map<int, int> m1;
vector<int> v;
int main() {
int n = 2010;
for(int i = 0; i < n; i++) {
int k= i;
for(int j = 0; j< 2000;j++) {
m[k]++;
k = k*k % n;
}
for(auto x : m) {
if(x.second >= 1) {
v.push_back(x.first);
}
}
m1[v.size()]++;
v.clear();
m.clear();
}
for(auto x : m1) {
cout << x.first << ' ' << x.second << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKbWFwPGludCxpbnQ+IG07Cm1hcDxpbnQsIGludD4gbTE7CnZlY3RvcjxpbnQ+IHY7CgoKaW50IG1haW4oKSB7CglpbnQgbiA9IDIwMTA7Cglmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CgkJaW50IGs9IGk7CgkJZm9yKGludCBqID0gMDsgIGo8IDIwMDA7aisrKSB7CgkJCW1ba10rKzsKCQkJayA9IGsqayAlIG47CgkJfQoJCQoJCWZvcihhdXRvIHggOiBtKSB7CgkJCWlmKHguc2Vjb25kID49IDEpIHsKCQkJCXYucHVzaF9iYWNrKHguZmlyc3QpOwoJCQl9CQoJCX0KCQkKCQltMVt2LnNpemUoKV0rKzsKCQl2LmNsZWFyKCk7CgkJbS5jbGVhcigpOwoJfQoJZm9yKGF1dG8geCA6IG0xKSB7CgkJY291dCA8PCB4LmZpcnN0IDw8ICcgJyA8PCB4LnNlY29uZCA8PCBlbmRsOwoJfQoJcmV0dXJuIDA7Cn0=