Problem: Volodya has recently visited a very odd town. There are N tourist attractions in the town and every two of them are connected by a bidirectional road. Each road has some travel price (natural number) assigned to it and all prices are distinct. But the most striking thing about this town is that each city sightseeing tour has the same total price! That is, if we choose any city sightseeing tour — a cycle which visits every attraction exactly once — the sum of the costs of the tour roads is independent of the tour. Volodya is curious if you can find such price system with all road prices not greater than 1000.

Input

Input contains just one natural number (3 ≤ N ≤ 20) — the number of town attractions.

Output

Output should contain N rows containing N positive integer numbers each — the adjacency matrix of the prices graph (thus, j-th number in i-th row should be equal to the price of the road between the j-th and the i-th attraction). Diagonal numbers should be equal to zero. All numbers should not be greater than 1000. All prices should be positive and pairwise distinct. If there are several solutions, output any of them.

Examples

Input

3


Output

0 3 4 
3 0 5 
4 5 0 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
int main() {
  int n;
  std::cin >> n;
  if (n == 3) {
    puts("0 3 4");
    puts("3 0 5");
    puts("4 5 0");
    return 0;
  }
  if (n == 4) {
    puts("0 3 1 2");
    puts("3 0 5 6");
    puts("1 5 0 4");
    puts("2 6 4 0");
    return 0;
  }
  if (n == 5) {
    puts("0 1 3 2 5");
    puts("1 0 7 6 9");
    puts("3 7 0 8 11");
    puts("2 6 8 0 10");
    puts("5 9 11 10 0");
    return 0;
  }
  if (n == 6) {
    puts("0 1 3 5 9 14");
    puts("1 0 2 4 8 13");
    puts("3 2 0 6 10 15");
    puts("5 4 6 0 12 17");
    puts("9 8 10 12 0 21");
    puts("14 13 15 17 21 0");
    return 0;
  }
  if (n == 7) {
    puts("0 1 3 5 9 14 23");
    puts("1 0 2 4 8 13 22");
    puts("3 2 0 6 10 15 24");
    puts("5 4 6 0 12 17 26");
    puts("9 8 10 12 0 21 30");
    puts("14 13 15 17 21 0 35");
    puts("23 22 24 26 30 35 0");
    return 0;
  }
  if (n == 8) {
    puts("0 1 3 5 9 14 23 37");
    puts("1 0 2 4 8 13 22 36");
    puts("3 2 0 6 10 15 24 38");
    puts("5 4 6 0 12 17 26 40");
    puts("9 8 10 12 0 21 30 44");
    puts("14 13 15 17 21 0 35 49");
    puts("23 22 24 26 30 35 0 58");
    puts("37 36 38 40 44 49 58 0");
    return 0;
  }
  if (n == 9) {
    puts("0 1 3 5 9 14 23 37 60");
    puts("1 0 2 4 8 13 22 36 59");
    puts("3 2 0 6 10 15 24 38 61");
    puts("5 4 6 0 12 17 26 40 63");
    puts("9 8 10 12 0 21 30 44 67");
    puts("14 13 15 17 21 0 35 49 72");
    puts("23 22 24 26 30 35 0 58 81");
    puts("37 36 38 40 44 49 58 0 95");
    puts("60 59 61 63 67 72 81 95 0");
    return 0;
  }
  if (n == 10) {
    puts("0 1 3 5 9 14 23 37 60 97");
    puts("1 0 2 4 8 13 22 36 59 96");
    puts("3 2 0 6 10 15 24 38 61 98");
    puts("5 4 6 0 12 17 26 40 63 100");
    puts("9 8 10 12 0 21 30 44 67 104");
    puts("14 13 15 17 21 0 35 49 72 109");
    puts("23 22 24 26 30 35 0 58 81 118");
    puts("37 36 38 40 44 49 58 0 95 132");
    puts("60 59 61 63 67 72 81 95 0 155");
    puts("97 96 98 100 104 109 118 132 155 0");
    return 0;
  }
  if (n == 11) {
    puts("0 1 3 5 9 14 23 37 60 97 107");
    puts("1 0 2 4 8 13 22 36 59 96 106");
    puts("3 2 0 6 10 15 24 38 61 98 108");
    puts("5 4 6 0 12 17 26 40 63 100 110");
    puts("9 8 10 12 0 21 30 44 67 104 114");
    puts("14 13 15 17 21 0 35 49 72 109 119");
    puts("23 22 24 26 30 35 0 58 81 118 128");
    puts("37 36 38 40 44 49 58 0 95 132 142");
    puts("60 59 61 63 67 72 81 95 0 155 165");
    puts("97 96 98 100 104 109 118 132 155 0 202");
    puts("107 106 108 110 114 119 128 142 165 202 0");
    return 0;
  }
  if (n == 12) {
    puts("0 1 3 5 9 14 23 37 60 97 107 204");
    puts("1 0 2 4 8 13 22 36 59 96 106 203");
    puts("3 2 0 6 10 15 24 38 61 98 108 205");
    puts("5 4 6 0 12 17 26 40 63 100 110 207");
    puts("9 8 10 12 0 21 30 44 67 104 114 211");
    puts("14 13 15 17 21 0 35 49 72 109 119 216");
    puts("23 22 24 26 30 35 0 58 81 118 128 225");
    puts("37 36 38 40 44 49 58 0 95 132 142 239");
    puts("60 59 61 63 67 72 81 95 0 155 165 262");
    puts("97 96 98 100 104 109 118 132 155 0 202 299");
    puts("107 106 108 110 114 119 128 142 165 202 0 309");
    puts("204 203 205 207 211 216 225 239 262 299 309 0");
    return 0;
  }
  if (n == 13) {
    puts("0 1 3 5 9 14 23 37 60 97 107 204 311");
    puts("1 0 2 4 8 13 22 36 59 96 106 203 310");
    puts("3 2 0 6 10 15 24 38 61 98 108 205 312");
    puts("5 4 6 0 12 17 26 40 63 100 110 207 314");
    puts("9 8 10 12 0 21 30 44 67 104 114 211 318");
    puts("14 13 15 17 21 0 35 49 72 109 119 216 323");
    puts("23 22 24 26 30 35 0 58 81 118 128 225 332");
    puts("37 36 38 40 44 49 58 0 95 132 142 239 346");
    puts("60 59 61 63 67 72 81 95 0 155 165 262 369");
    puts("97 96 98 100 104 109 118 132 155 0 202 299 406");
    puts("107 106 108 110 114 119 128 142 165 202 0 309 416");
    puts("204 203 205 207 211 216 225 239 262 299 309 0 513");
    puts("311 310 312 314 318 323 332 346 369 406 416 513 0");
    return 0;
  }
  if (n == 14) {
    puts("0 1 3 5 9 14 23 37 60 97 107 204 311 122");
    puts("1 0 2 4 8 13 22 36 59 96 106 203 310 121");
    puts("3 2 0 6 10 15 24 38 61 98 108 205 312 123");
    puts("5 4 6 0 12 17 26 40 63 100 110 207 314 125");
    puts("9 8 10 12 0 21 30 44 67 104 114 211 318 129");
    puts("14 13 15 17 21 0 35 49 72 109 119 216 323 134");
    puts("23 22 24 26 30 35 0 58 81 118 128 225 332 143");
    puts("37 36 38 40 44 49 58 0 95 132 142 239 346 157");
    puts("60 59 61 63 67 72 81 95 0 155 165 262 369 180");
    puts("97 96 98 100 104 109 118 132 155 0 202 299 406 217");
    puts("107 106 108 110 114 119 128 142 165 202 0 309 416 227");
    puts("204 203 205 207 211 216 225 239 262 299 309 0 513 324");
    puts("311 310 312 314 318 323 332 346 369 406 416 513 0 431");
    puts("122 121 123 125 129 134 143 157 180 217 227 324 431 0");
    return 0;
  }
  if (n == 15) {
    puts("0 1 3 5 9 14 23 37 60 97 107 204 311 122 230");
    puts("1 0 2 4 8 13 22 36 59 96 106 203 310 121 229");
    puts("3 2 0 6 10 15 24 38 61 98 108 205 312 123 231");
    puts("5 4 6 0 12 17 26 40 63 100 110 207 314 125 233");
    puts("9 8 10 12 0 21 30 44 67 104 114 211 318 129 237");
    puts("14 13 15 17 21 0 35 49 72 109 119 216 323 134 242");
    puts("23 22 24 26 30 35 0 58 81 118 128 225 332 143 251");
    puts("37 36 38 40 44 49 58 0 95 132 142 239 346 157 265");
    puts("60 59 61 63 67 72 81 95 0 155 165 262 369 180 288");
    puts("97 96 98 100 104 109 118 132 155 0 202 299 406 217 325");
    puts("107 106 108 110 114 119 128 142 165 202 0 309 416 227 335");
    puts("204 203 205 207 211 216 225 239 262 299 309 0 513 324 432");
    puts("311 310 312 314 318 323 332 346 369 406 416 513 0 431 539");
    puts("122 121 123 125 129 134 143 157 180 217 227 324 431 0 350");
    puts("230 229 231 233 237 242 251 265 288 325 335 432 539 350 0");
    return 0;
  }
  if (n == 16) {
    puts("0 1 3 5 9 14 23 37 60 97 107 204 311 122 230 435");
    puts("1 0 2 4 8 13 22 36 59 96 106 203 310 121 229 434");
    puts("3 2 0 6 10 15 24 38 61 98 108 205 312 123 231 436");
    puts("5 4 6 0 12 17 26 40 63 100 110 207 314 125 233 438");
    puts("9 8 10 12 0 21 30 44 67 104 114 211 318 129 237 442");
    puts("14 13 15 17 21 0 35 49 72 109 119 216 323 134 242 447");
    puts("23 22 24 26 30 35 0 58 81 118 128 225 332 143 251 456");
    puts("37 36 38 40 44 49 58 0 95 132 142 239 346 157 265 470");
    puts("60 59 61 63 67 72 81 95 0 155 165 262 369 180 288 493");
    puts("97 96 98 100 104 109 118 132 155 0 202 299 406 217 325 530");
    puts("107 106 108 110 114 119 128 142 165 202 0 309 416 227 335 540");
    puts("204 203 205 207 211 216 225 239 262 299 309 0 513 324 432 637");
    puts("311 310 312 314 318 323 332 346 369 406 416 513 0 431 539 744");
    puts("122 121 123 125 129 134 143 157 180 217 227 324 431 0 350 555");
    puts("230 229 231 233 237 242 251 265 288 325 335 432 539 350 0 663");
    puts("435 434 436 438 442 447 456 470 493 530 540 637 744 555 663 0");
    return 0;
  }
  if (n == 17) {
    puts("0 1 3 5 9 14 23 37 60 97 107 204 311 122 230 435 567");
    puts("1 0 2 4 8 13 22 36 59 96 106 203 310 121 229 434 566");
    puts("3 2 0 6 10 15 24 38 61 98 108 205 312 123 231 436 568");
    puts("5 4 6 0 12 17 26 40 63 100 110 207 314 125 233 438 570");
    puts("9 8 10 12 0 21 30 44 67 104 114 211 318 129 237 442 574");
    puts("14 13 15 17 21 0 35 49 72 109 119 216 323 134 242 447 579");
    puts("23 22 24 26 30 35 0 58 81 118 128 225 332 143 251 456 588");
    puts("37 36 38 40 44 49 58 0 95 132 142 239 346 157 265 470 602");
    puts("60 59 61 63 67 72 81 95 0 155 165 262 369 180 288 493 625");
    puts("97 96 98 100 104 109 118 132 155 0 202 299 406 217 325 530 662");
    puts("107 106 108 110 114 119 128 142 165 202 0 309 416 227 335 540 672");
    puts("204 203 205 207 211 216 225 239 262 299 309 0 513 324 432 637 769");
    puts("311 310 312 314 318 323 332 346 369 406 416 513 0 431 539 744 876");
    puts("122 121 123 125 129 134 143 157 180 217 227 324 431 0 350 555 687");
    puts("230 229 231 233 237 242 251 265 288 325 335 432 539 350 0 663 795");
    puts("435 434 436 438 442 447 456 470 493 530 540 637 744 555 663 0 1000");
    puts("567 566 568 570 574 579 588 602 625 662 672 769 876 687 795 1000 0");
    return 0;
  }
  if (n == 18) {
    puts("0 1 3 5 9 14 23 37 60 97 107 204 311 122 230 435 567 185");
    puts("1 0 2 4 8 13 22 36 59 96 106 203 310 121 229 434 566 184");
    puts("3 2 0 6 10 15 24 38 61 98 108 205 312 123 231 436 568 186");
    puts("5 4 6 0 12 17 26 40 63 100 110 207 314 125 233 438 570 188");
    puts("9 8 10 12 0 21 30 44 67 104 114 211 318 129 237 442 574 192");
    puts("14 13 15 17 21 0 35 49 72 109 119 216 323 134 242 447 579 197");
    puts("23 22 24 26 30 35 0 58 81 118 128 225 332 143 251 456 588 206");
    puts("37 36 38 40 44 49 58 0 95 132 142 239 346 157 265 470 602 220");
    puts("60 59 61 63 67 72 81 95 0 155 165 262 369 180 288 493 625 243");
    puts("97 96 98 100 104 109 118 132 155 0 202 299 406 217 325 530 662 280");
    puts(
        "107 106 108 110 114 119 128 142 165 202 0 309 416 227 335 540 672 "
        "290");
    puts(
        "204 203 205 207 211 216 225 239 262 299 309 0 513 324 432 637 769 "
        "387");
    puts(
        "311 310 312 314 318 323 332 346 369 406 416 513 0 431 539 744 876 "
        "494");
    puts(
        "122 121 123 125 129 134 143 157 180 217 227 324 431 0 350 555 687 "
        "305");
    puts(
        "230 229 231 233 237 242 251 265 288 325 335 432 539 350 0 663 795 "
        "413");
    puts(
        "435 434 436 438 442 447 456 470 493 530 540 637 744 555 663 0 1000 "
        "618");
    puts(
        "567 566 568 570 574 579 588 602 625 662 672 769 876 687 795 1000 0 "
        "750");
    puts(
        "185 184 186 188 192 197 206 220 243 280 290 387 494 305 413 618 750 "
        "0");
    return 0;
  }
  if (n == 19) {
    puts("0 1 3 5 9 14 23 37 60 97 107 204 311 122 230 435 567 185 271");
    puts("1 0 2 4 8 13 22 36 59 96 106 203 310 121 229 434 566 184 270");
    puts("3 2 0 6 10 15 24 38 61 98 108 205 312 123 231 436 568 186 272");
    puts("5 4 6 0 12 17 26 40 63 100 110 207 314 125 233 438 570 188 274");
    puts("9 8 10 12 0 21 30 44 67 104 114 211 318 129 237 442 574 192 278");
    puts("14 13 15 17 21 0 35 49 72 109 119 216 323 134 242 447 579 197 283");
    puts("23 22 24 26 30 35 0 58 81 118 128 225 332 143 251 456 588 206 292");
    puts("37 36 38 40 44 49 58 0 95 132 142 239 346 157 265 470 602 220 306");
    puts("60 59 61 63 67 72 81 95 0 155 165 262 369 180 288 493 625 243 329");
    puts(
        "97 96 98 100 104 109 118 132 155 0 202 299 406 217 325 530 662 280 "
        "366");
    puts(
        "107 106 108 110 114 119 128 142 165 202 0 309 416 227 335 540 672 290 "
        "376");
    puts(
        "204 203 205 207 211 216 225 239 262 299 309 0 513 324 432 637 769 387 "
        "473");
    puts(
        "311 310 312 314 318 323 332 346 369 406 416 513 0 431 539 744 876 494 "
        "580");
    puts(
        "122 121 123 125 129 134 143 157 180 217 227 324 431 0 350 555 687 305 "
        "391");
    puts(
        "230 229 231 233 237 242 251 265 288 325 335 432 539 350 0 663 795 413 "
        "499");
    puts(
        "435 434 436 438 442 447 456 470 493 530 540 637 744 555 663 0 1000 "
        "618 704");
    puts(
        "567 566 568 570 574 579 588 602 625 662 672 769 876 687 795 1000 0 "
        "750 836");
    puts(
        "185 184 186 188 192 197 206 220 243 280 290 387 494 305 413 618 750 0 "
        "454");
    puts(
        "271 270 272 274 278 283 292 306 329 366 376 473 580 391 499 704 836 "
        "454 0");
    return 0;
  }
  if (n == 20) {
    puts("0 1 3 5 9 14 23 37 60 97 107 204 311 122 230 435 567 185 271 295");
    puts("1 0 2 4 8 13 22 36 59 96 106 203 310 121 229 434 566 184 270 294");
    puts("3 2 0 6 10 15 24 38 61 98 108 205 312 123 231 436 568 186 272 296");
    puts("5 4 6 0 12 17 26 40 63 100 110 207 314 125 233 438 570 188 274 298");
    puts("9 8 10 12 0 21 30 44 67 104 114 211 318 129 237 442 574 192 278 302");
    puts(
        "14 13 15 17 21 0 35 49 72 109 119 216 323 134 242 447 579 197 283 "
        "307");
    puts(
        "23 22 24 26 30 35 0 58 81 118 128 225 332 143 251 456 588 206 292 "
        "316");
    puts(
        "37 36 38 40 44 49 58 0 95 132 142 239 346 157 265 470 602 220 306 "
        "330");
    puts(
        "60 59 61 63 67 72 81 95 0 155 165 262 369 180 288 493 625 243 329 "
        "353");
    puts(
        "97 96 98 100 104 109 118 132 155 0 202 299 406 217 325 530 662 280 "
        "366 390");
    puts(
        "107 106 108 110 114 119 128 142 165 202 0 309 416 227 335 540 672 290 "
        "376 400");
    puts(
        "204 203 205 207 211 216 225 239 262 299 309 0 513 324 432 637 769 387 "
        "473 497");
    puts(
        "311 310 312 314 318 323 332 346 369 406 416 513 0 431 539 744 876 494 "
        "580 604");
    puts(
        "122 121 123 125 129 134 143 157 180 217 227 324 431 0 350 555 687 305 "
        "391 415");
    puts(
        "230 229 231 233 237 242 251 265 288 325 335 432 539 350 0 663 795 413 "
        "499 523");
    puts(
        "435 434 436 438 442 447 456 470 493 530 540 637 744 555 663 0 1000 "
        "618 704 728");
    puts(
        "567 566 568 570 574 579 588 602 625 662 672 769 876 687 795 1000 0 "
        "750 836 860");
    puts(
        "185 184 186 188 192 197 206 220 243 280 290 387 494 305 413 618 750 0 "
        "454 478");
    puts(
        "271 270 272 274 278 283 292 306 329 366 376 473 580 391 499 704 836 "
        "454 0 564");
    puts(
        "295 294 296 298 302 307 316 330 353 390 400 497 604 415 523 728 860 "
        "478 564 0");
    return 0;
  }
  return 0;
}