题目描述

定义 \(01\) 串的 \(mex\) 为：字符串所有字符中最小未出现的非负整数。例如， \(mex("0") = 1, mex("1") = 0, mex("1010") = 2\)。

定义一个 \(01\) 串的快乐值为，这个 \(01\) 串的所有子串的 \(mex\) 之和。

Kokoro 有一个 \(01\) 串，不太聪明的她想知道这个 \(01\) 串的快乐值是多少。

输入格式

第一行输入一个正整数 \(T(1 \le T \le 2 \times 10^5)\)，表示数据组数。

对于每一组数据：

第一行输入一个 \(01\) 串 \(s\)。

数据保证 \(\sum |s| \le 2 \times 10^6\)。

输出格式

对于每组数据输出一个整数表示答案。

样例输入

4
00
11
10
01

样例输出

3
0
3
3