def solve(n, mod):
    # 特別なケース
    if n == 1:
        return 1
    
    # 高速累乗計算（mod付き）
    def pow_mod(x, y, mod):
        result = 1
        x = x % mod
        while y > 0:
            if y % 2 == 1:
                result = (result * x) % mod
            y = y // 2
            x = (x * x) % mod
        return result
    
    # 巡回置換の数を計算
    def count_cycles(n):
        cycles = [0] * (n + 1)
        for i in range(1, n + 1):
            for j in range(i, n + 1, i):
                cycles[j] = (cycles[j] + pow_mod(i, mod - 2, mod)) % mod
        return cycles
    
    # 順列の数を計算
    fact = [1]
    for i in range(1, n + 1):
        fact.append((fact[-1] * i) % mod)
    
    # 軌道の数と大きさを計算
    cycles = count_cycles(n)
    
    # 結果を計算
    result = 0
    for i in range(1, n + 1):
        orbit_size = (n // i) * 2  # 各軌道のサイズ
        orbit_count = (fact[n] * cycles[i]) % mod  # 軌道の数
        result = (result + orbit_count * orbit_size) % mod
    
    return result

def main():
    t, m = map(int, input().split())
    results = []
    
    for _ in range(t):
        n = int(input())
        results.append(solve(n, m))
    
    for result in results:
        print(result)

if __name__ == "__main__":
    main()