给你一个度为K的N个点的树，或者说，每个点至多有K个儿子。这棵树是“最低能量”的：这些点当且仅当上一层排满以后，才会在这一层从左往右排。这些点的序号也是有序的，从1开始。比如有：

你需要输出Q个询问的答案，形式是x y，表示询问从点x走到点y的最小步数是多少。

第一行包含三个整数N,K,Q（N<=10^15,1<=K<=1000,1<=Q<=100000）

接下来Q行，每行两个整数x,y（1<=x,y<=N,x≠y）

共Q行，一行一个答案。