1. #include<bits/stdc++.h>
2. using namespace std;
3. int n;
4. array<int,4> ans;
5. int rem[10][150005];
6. int lmp[10][100005], rmp[10][100005];
7. bool operator<(array<int,4> a, array<int,4> b){
8.         if(b[0] == 0) return true;
9.         assert(a[0] + a[2] == b[0] + b[2]);
10.         if(a[1] != b[1]) return a[1] < b[1];
11.         if(b[0] > a[0]) return a[3] < b[1];
12.         else if(a[0] > b[0])return a[1] < b[3];
13.         else return a[3] < b[3];
14. }
15.  
16. int toint(array<int,4> ar){
17.         if(ar[0]+ar[2] > 6) return -1;
18.         int ans = 0;
19.         for(int i=0;i<ar[0];i++) ans = ans*10+ar[1];
20.         for(int i=0;i<ar[2];i++) ans = ans*10+ar[3];
21.         return ans;
22. }
23.  
24. void solve(){
25.         ans = {0, 0, 0, 0};
26.         memset(lmp, 0, sizeof(lmp));
27.         memset(rmp, 0x3f, sizeof(rmp));
28.         for(int i=1;i<=9;i++){
29.                 for(int j=1;j<=150000;j++){
30.                         rem[i][j] = (rem[i][j-1] * 10 + i) % n;
31.                 }
32.         }
33.         for(int i=1;i<=9;i++) lmp[i][rem[i][1]] = rmp[i][rem[i][1]] = 1;
34.         for(int dig=2;dig<=100005;dig++){
35.                 for(int i=1;i<=9;i++){
36.                         int re = rem[i][dig];
37.                         for(int j=1;j<=i;j++){
38.                                 if(lmp[j][re] > 0){
39.                                         array<int, 4> ar = {dig - lmp[j][re], i, lmp[j][re],i-j};
40.                                         if(toint(ar) != n && (ans[0] == 0 || ar < ans)) ans = ar;
41.                                 }
42.                         }
43.                         re = (n - re) % n;
44.                         for(int j=1;i+j<10;j++){
45.                                 if(rmp[j][re] < dig){
46.                                         array<int, 4> ar = {dig - rmp[j][re], i, rmp[j][re],i+j};
47.                                         if(toint(ar) != n && (ans[0] == 0 || ar < ans)) ans = ar;
48.                                 }
49.                         }
50.                 }
51.                 if(ans[0] != 0){
52.                         cout<<n<<": "<<ans[0]<<" "<<ans[1]<<" "<<ans[2]<<" "<<ans[3]<<'\n';
53.                         return;
54.                 }
55.                 for(int i=1;i<=9;i++){
56.                         lmp[i][rem[i][dig]] = max(lmp[i][rem[i][dig]], dig);
57.                         rmp[i][rem[i][dig]] = min(rmp[i][rem[i][dig]], dig);
58.                 }
59.         }
60. }
61.  
62. int main(){
63.         ios::sync_with_stdio(0), cin.tie(0);
64.         while(cin>>n){
65.                 if(n==0) break;
66.                 solve();
67.         }
68. }
69.