#include<iostream>
#include<fstream>
#include<vector>
#define N 10000

int gcd(int q1,int p1){
    if(q1%p1==0) return p1;
    return gcd(p1,q1%p1);
}

int sosu(int j){
    if(j<2)return 0;
    if(j==2)return 1;
    if(j%2==0)return 0;
    for(int i=3; i<=j/2; i++){
        if(j%i==0)return 0;
    }
    return 1;
}

int main(){
    std::vector<int> n;
    n.resize(N);
