题目背景

“看着我的眼睛。”一一优祖列罕

题目描述

VOID 抽取的基因呈环形，每个单元用 A 到 Z 的大写字母表示，换句话说一个基因就是一个环状字符串。设环状基因长度为 $l_i$，从其中 $l_i$ 个断点分别断开，可以形成 $l_i$ 种链状基因（不一定两两不同）。以 ABCAB 为例，链状基因分别为 ABCAB，BCABA，CABAB，ABABC，BABCA，依次编号 $1-5$ 现要抽取其中一种链状基因，不同种类基因参数不尽相同，每个环状基因有两个参数 $p_i,t_i$ 首先执行打乱操作，每个位置 $x$ 设定权重

对于任意 $x,y$，当 $F(x)<f(y)$ 且编号 $x$ 的链状基因字典序小于编号 $y$ 的链状基因字典序时，这两个链状基因会交换编号。输入数据保证存在一种方案使得该操作不会执行超过 $f$ 次便会停止。（易知执行顺序不影响最终结果）最终，选取编号 $p_i$ 的链状基因作为该环状基因的采样，记为 $g_i$。现在有 $n$ 个环状基因。$a$ 环状基因是 $b$ 环状基因的亲和体，当且仅当 $a$ 环状基因的采样为 $b$ 环状基因采样的前缀。求每个环状基因的亲和体数量。

输入格式

第一行一个数 $n$，表示环状基因的数量。

接下来 $n$ 行，每行描述一个环状基因，由一个字符串，$p_i,t_i$ 组成，之间用空格分隔。

输出格式

输出 $n$ 行，每行一个数，表示该环状基因的亲和体数量。

样例输入

4
CDEAB 3 2
ABC 2 4
D 1 6
EDEE 2 6

样例输出

1
0
0
1

样例解释

数据范围与约定

对于 $100\%$ 的数据，$1\le p_i\le l_i$，$1\le t_i\le 10^4$。