package coinJam

import java.io.File
import java.io.PrintStream
import java.math.BigInteger
import java.util.*
import kotlin.concurrent.timer
import kotlin.system.measureNanoTime
import kotlin.system.measureTimeMillis

val out = PrintStream("out.txt")
val random = Random()

fun main(args : Array<String>) {
    val file = File(args[0]).bufferedReader()
    println(measureTimeMillis{
        for (i in 1..file.readLine().toInt()) {
            val input = file.readLine().split(' ').map { it.toInt() }
            solution(i, input[0], input[1])
        }
    })
}

fun solution(case : Int, n : Int, j : Int) {
    out.println("Case #$case:")
    val composites = mutableListOf<String>()
    primeLoop@while (composites.size < j) {
        var composite = randomNumber(n)
        if (composite in composites) {
            continue@primeLoop
        }
        var factors = mutableListOf<Int>()
        radixLoop@for (radix in 2..10) {
            var number = BigInteger(composite, radix)
            for (i in 2..100) {
                if (BigInteger.valueOf((i * i).toLong()) > number) {
                    continue@primeLoop
                }
                if (number % BigInteger.valueOf(i.toLong()) == BigInteger.ZERO) {
                    factors.add(i)
                    continue@radixLoop
                }
            }
            continue@primeLoop
        }
        composites.add(composite)
        out.println(composite + " " + factors.joinToString(separator = " ") { it.toString() })
    }
}

fun randomNumber(length : Int): String {
    var builder = StringBuilder()

    builder.append(1)
    for (i in 1..(length - 2)) {
        builder.append(random.nextInt(2))
    }
    builder.append(1)

    return builder.toString()
}