import io import sys from collections import defaultdict, deque, Counter from itertools import permutations, combinations, accumulate from heapq import heappush, heappop from bisect import bisect_right, bisect_left from math import gcd import math _INPUT = """\ 6 1 1 90 80 1 2 100 0 2 3 100 100 4 50 50 """ def Eratosthenes(n): prime=[] furui=list(range(2,n+1)) while furui[0]