fun main() {
    val ans = IntArray(101) { Int.MAX_VALUE }
    ans[0] = 0
    for (i in ans.indices) {
        for ((d, c) in listOf(1 to 1, 3 to 0, 5 to 0)) {
            if (i + d in ans.indices) ans[i + d] = minOf(ans[i + d], ans[i] + c)
        }
    }
    repeat(readInt()) {
        println(ans[readInt()])
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

fun main() {
    repeat(readInt()) {
        val (k, m) = readInts()
        println(maxOf(0, 2 * k - (m % (3 * k))))
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

fun main() {
    repeat(readInt()) {
        val (n, k) = readLongs()
        println(n - k.countTrailingZeroBits())
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

fun main() {
    repeat(readInt()) {
        readInt()
        val d = mutableListOf(mutableListOf<Long>())
        for (i in readLongs()) {
            if (i == 0L) {
                d.add(mutableListOf())
            } else {
                d.last().add(i)
            }
        }
        println(d.sumOf { l -> 2 * l.sum() - ((l.indices step 2).takeIf { l.size % 2 == 1 }?.maxOfOrNull { l[it] } ?: 0) })
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

private fun solve(): String {
    val (n, k) = readInts()
    var ans = listOf(n - 1, n)
    repeat(k - 1) {
        val min = ans.min()
        val prevStart = min - ans.size + 1
        if (prevStart <= 0) {
            return "-1"
        }
        ans = ans.zip(prevStart .. min).flatMap { (a, b) -> listOf(a, b) }.dropLast(1)
    }
    ans = (1 until ans.min()) + ans
    return ans.joinToString(" ")
}
fun main() {
    repeat(readInt()) {
        println(solve())
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

private const val MOD =  1000000007

@JvmInline
@Suppress("NOTHING_TO_INLINE")
private value class ModInt(val x: Int) {
    inline operator fun plus(other: ModInt) = ModInt((x + other.x).let { if (it >= MOD) it - MOD else it })
    inline operator fun minus(other: ModInt) = ModInt((x - other.x).let { if (it < 0) it + MOD else it })
    inline operator fun times(other: ModInt) = ModInt((x.toLong() * other.x % MOD).toInt())
    fun power(p_: Int): ModInt {
        var a = this
        var res = ModInt(1)
        var p = p_
        while (p != 0) {
            if ((p and 1) == 1) res *= a
            a *= a
            p = p shr 1
        }
        return res
    }

    inline operator fun div(other: ModInt) = this * other.inv()
    inline fun inv() = power(MOD - 2)

    companion object {
        inline fun from(x: Int) = ModInt((x % MOD + MOD) % MOD)
        inline fun from(x: Long) = ModInt(((x % MOD).toInt() + MOD) % MOD)
    }
}

@JvmInline
private value class ModIntArray(val storage:IntArray) {
    operator fun get(index: Int) = ModInt(storage[index])
    operator fun set(index: Int, value: ModInt) { storage[index] = value.x }
    val size get() = storage.size
}
private inline fun ModIntArray(n: Int, init: (Int) -> ModInt) = ModIntArray(IntArray(n) { init(it).x })

private const val COMB_MAX = 400_010

private val fs = ModIntArray(COMB_MAX) { ModInt(1) }.apply {
    for (i in 1 until size) {
        set(i, get(i - 1) * ModInt.from(i))
    }
}
private val ifs = ModIntArray(COMB_MAX) { fs[it].inv() }

private fun cnk(n: Int, k: Int) = if (n >= k) fs[n] * ifs[k] * ifs[n - k] else ModInt(0)

fun main() {
    val (n, k) = readInts()
    val ans = ModIntArray(n + 1) { ModInt(0) }

    for (diff in -n..n) {
        val ways = maxOf(0, diff - 1)
        val ll = maxOf(1, diff)
        val rr = minOf(n, n - 1 + diff)
        ans[ways] += ModInt(maxOf(0, rr - ll)) * cnk(n - diff - 1, k - 2)
    }
    for (i in 1 until n) {
        ans[i] += cnk(n - i - 1, k - 1)
    }
    for (j in 0 until n - 1) {
        ans[n - j - 1] += cnk(j, k - 1)
    }
    println(ans.storage.joinToString(" "))
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

import kotlin.math.abs
import kotlin.math.sign

fun main() {
    readInts()
    val x = readInts()
    val h = readInts()
    val ord = buildList {
        for (i in x.indices.sortedBy { x[it] }) {
            while (isNotEmpty() && h[i] - h[last()] >= x[i] - x[last()]) {
                removeLast()
            }
            if (isEmpty() || h[last()] - h[i] <= x[i] - x[last()]) {
                add(i)
            }
        }
    }.map { x[it] to h[it] }

    fun nextAfter(pos: Int) = ord.binarySearch { (x, _) -> if (x >= pos) 1 else -1 }.inv()
    fun coverBy(idx: Int, pos: Int) = ord.getOrNull(idx)?.let { (x, h) -> maxOf(0, abs(x - pos) - h) } ?: Int.MAX_VALUE
    fun cover(pos: Int): Int {
        val a = nextAfter(pos)
        return minOf(coverBy(a - 1, pos), coverBy(a, pos))
    }

    fun cover2(l: Int, r: Int): Int {
        val a = nextAfter((l + r) / 2)
        return minOf(maxOf(coverBy(a, l), coverBy(a, r)), maxOf(coverBy(a - 1, l), coverBy(a - 1, r)))
    }

    val ans = List(readInt()) {
        val (l, r) = readInts()
        minOf(
            cover(l) + cover(r),
            cover2(l, r)
        )
    }
    println(ans.joinToString(" "))
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

import java.math.BigInteger

fun main() = repeat(readLine()!!.toInt()) {
  val (n, hp) = readLine()!!.split(" ").let { (n, hp) -> n.toInt() to BigInteger(hp) } 
  val s = readLine()!!.split(" ").map { BigInteger(it) }
  val m = readLine()!!.toInt()
  val c = Array(m) { readLine()!!.split(" ").drop(1).map { it.toInt() - 1 } }
  val delta = Array(m) { BigInteger.ZERO }
  val minDelta = Array(m) { BigInteger.ZERO }
  for (i in 0 until m) {
    var curHP = BigInteger.ZERO
    for (id in c[i]) {
      if (id < n) {
        curHP += s[id]
        minDelta[i] = minOf(minDelta[i], curHP)
      } else {
        minDelta[i] = minOf(minDelta[i], curHP + minDelta[id - n])
        curHP += delta[id - n]
      }
    }
    delta[i] = curHP
  }
  
  fun rec(remHP : BigInteger, idCompSpell : Int) : Int {
    var curHP = remHP
    for (id in c[idCompSpell]) {
      if (id < n) {
        curHP += s[id]
        if (curHP <= BigInteger.ZERO)
          return id + 1
      } else {
        if (curHP + minDelta[id - n] <= BigInteger.ZERO)
          return rec(curHP, id - n)
        curHP += delta[id - n]
      }
    }
    return -1
  }
  
  println(rec(hp, m - 1))
}

fun readTree(n: Int) : List<BooleanArray> {
    val p = listOf(null) + readInts().map { it - 1 }
    return List(n) { a -> BooleanArray(n) { b -> a in generateSequence(b) { p[it] } } }
}
fun main() {
    val n = readInt()
    val t1 = readTree(n)
    val t2 = readTree(n)
    val masks = LongArray(n) { a ->
        (0 until n).filter { b -> a != b && t1[a][b] == t2[a][b] && t1[b][a] == t2[b][a] }.sumOf { 1L shl it }
    }
    val data = mutableMapOf<Long, Int>()
    data[0] = 0
    fun compute(mask: Long) : Int = data.getOrPut(mask) {
        val index = mask.countTrailingZeroBits()
        maxOf(compute(mask xor (1L shl index)), compute(mask and masks[index]) + 1)
    }
    println(2 * (n - compute((1L shl n) - 1)))
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

const val M = 1000
const val K = 10

fun main() {  
  val (n, q) = readLine()!!.split(" ").map { it.toInt() }
  val a = readLine()!!.split(" ").map { it.toInt() }
  val b = readLine()!!.split(" ").map { it.toInt() }
  val l = IntArray(q)
  val r = IntArray(q)
  for (i in 0 until q) {
    val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1}
    l[i] = x
    r[i] = y
  }
  val s = b.scan(0, Int::plus)
  val ev = Array(n) { mutableListOf<Int>() }
  for (i in 0 until n) {
    for (j in 1 until K) {
      val x = s[i] - (a[i] + j - 1) / j + 1
      val pos = s.binarySearch { if (it < x) -1 else 1 }.inv()
      if (pos < i) ev[pos].add(i)
    }
  }
  val qr = Array(n) { mutableListOf<Int>() }
  for (i in 0 until q) qr[l[i]].add(i)
  val f = IntArray(n) { 0 }
  fun inc(i : Int) = generateSequence(i) { (it or (it + 1)).takeIf { it < n } }.forEach { ++f[it] }
  fun sum(i : Int) = generateSequence(i) { ((it and (it + 1)) - 1).takeIf { it >= 0 } }.sumOf { f[it] }
  for (i in 0 until n) inc(i)
  val ans = IntArray(q) { 0 }
  for (i in 0 until n) {
    for (j in ev[i]) inc(j)
    for (j in qr[i]) {
      var cur = b[l[j]]
      for (x in 1 until M.coerceAtMost(r[j] - l[j] + 1)) {
        ans[j] += (a[l[j] + x] + cur - 1) / cur
        cur += b[l[j] + x]
      }
      if (l[j] + M <= r[j]) ans[j] += sum(r[j]) - sum(l[j] + M - 1)
    }
  }
  println(ans.joinToString("\n"))
}