题目描述

爱丽丝正在探索一个危险的大型迷宫。迷宫包含 $n$ 个洞穴和 $m$ 条单向通道，每条通道形如 $(u,v,d)$ ，表示可以从洞穴 $u$ 走到洞穴 $v$ ，其难度值为 $d$ 。整个迷宫可以视作一个带权有向图。

爱丽丝初始有 $x$ 点体力值。若通过一条难度为 $d$ 的通道，则体力会变为

\left\lfloor \frac{x}{d} \right\rfloor

当体力降为 $0$ 时，她无法继续探索。

由于爱丽丝方向感很差，她提出若干询问：若从洞穴 $p_i$ 出发，初始体力为 $x_i$ ，并且每一步都会随机选择一条可走的通道，那么在体力耗尽之前，她一定会经过的最少通道数是多少。允许重复经过同一条通道，重复经过时体力仍然会继续消耗。

输入格式

从标准输入按以下格式读取数据：

$n$ $m$ $Q$

接下来 $m$ 行，每行三个整数 $u$ $v$ $d$

接下来 $Q$ 行，每行两个整数 $p_i$ $x_i$

其中：

输出若干行，每行一个整数，表示对应询问的答案。

测试点编号	$n \le$	$m \le$	$Q \le$	特殊性质
$1 \sim 6$	$100$	$200$	$100$	无
$7 \sim 12$	$5000$	$10000$	$5000$	无
$13 \sim 14$	$5000$	$10000$	$5000$	有
$15 \sim 20$	$2 \times 10^5$	$5 \times 10^5$	$2 \times 10^5$	无

特殊性质：所有通道的 $d$ 都等于 $10^9$ 。