Divisible Sub-parts of Five-Digit Numbers

Given a five-digit number \(\overline{a_1a_2a_3a_4a_5}\), we define three sub-numbers as follows:

\(sub_1 = \overline{a_1a_2a_3}\)

\(sub_2 = \overline{a_2a_3a_4}\)

\(sub_3 = \overline{a_3a_4a_5}\)

For example, the number \(20207\) can be split into \(sub_1=202\), \(sub_2=020\; (\text{which is }20)\), and \(sub_3=207\).

You are given a positive integer \(K\). Your task is to find all five-digit numbers between 10000 and 30000 (inclusive) such that all three sub-numbers \(sub_1, sub_2,\) and \(sub_3\) are divisible by \(K\).

inputFormat

The input consists of a single integer \(K\).

outputFormat

Print each valid five-digit number in ascending order, each on a new line.

sample

10

10000
11000
12000
13000
14000
15000
16000
17000
18000
19000
20000
21000
22000
23000
24000
25000
26000
27000
28000
29000
30000