Under construction

Still being built. Things may change

Hyper Fake Chocolate Number

Time limit1sMemory limit1024 MB

Summary
Find 11 primes between 10^7 and 10^8 whose product is a Carmichael number, so that a^(N-1) mod N is 1 for every base a coprime to N.
Level

Medium7 of 10

Topics
Number theory, Math
Solved
No attempts yet

Problem

Coco, who loves chocolate and number games, defined a "chocolate number" as follows.

  • A positive integer n>1n>1 is a chocolate number if it is divisible only by 11 and itself.

Soon after, Coco discovered "Coco's theorem."

  • If pp is a chocolate number, then ap−1mod⁡p=1a^{p-1}\operatorname{mod} p=1 for every integer aa coprime to pp.

Coco then came up with a way to test whether a number is a chocolate number using this theorem. The method is as follows.

  • If ap−1mod⁡p=1a^{p-1}\operatorname{mod} p=1 for every integer aa coprime to pp, then pp is a chocolate number.

However, not long after, Coco found that 561 satisfies this test but is not a chocolate number. Coco called such numbers "fake chocolate numbers" and began studying how to find them.

Neglecting the chocolate factory, Coco focused on this research. Coco found fake chocolate numbers that are products of 3, 4, ..., 10 chocolate numbers, but could not find one that is a product of 11. Finding any one is not hard, so find a number NN that satisfies the following condition.

  • Write N=a1×a2×⋯×a11N=a_1\times a_2\times\cdots\times a_{11}. Then NN is a fake chocolate number, and for each 1≤i≤111\le i\le 11, aia_i is a chocolate number with 107≤ai<10810^7\le a_i<10^8.

Input

There is no input.

Output

Write the 11 chocolate numbers whose product satisfies the condition above on the first line, in ascending order, separated by spaces.

Examples1

  1. Example 1

    Input
    Expected output
    2 3 5 7 11 13 17 19 23 29 31