L. Monther's Birthday
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Monther always struggles with precision errors. To help him, Ahmad gave him a bunch of pairs and asked him the following.

What's the number of pairs $$$(i \lt j)$$$ such that $$$d(a_i, b_i)=d(a_j, b_j)$$$, where $$$d(a_i, b_i)$$$ is the decimal representation after the decimal point of the value $$$(\frac{a_i}{b_i})$$$.

I.e. $$$d(1, 2) = 5$$$, $$$d(2, 3) = 666666\ldots$$$, $$$d(5, 2) = 5$$$.

Note that two values are equal only if they're equal to infinitely many digits.

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.

Then for each test case, the first line contains an integer $$$n$$$ $$$(1 \leq n \leq 3\cdot10^5)$$$ – the number of pairs in the array.

The next $$$n$$$ lines of the case, each, contain two integers $$$a_i$$$ $$$b_i$$$ $$$(1 \leq a_i, b_i \leq 10^{18})$$$.

It's guaranteed that the sum of $$$n$$$ over all test cases is not greater than $$$2\cdot10^6$$$.

Output

For each test case, print one integer, the number of pairs as described in the statement.

Example
Input
2
4
1 2
2 3
5 2
11 3
5
2 3
4 5
3 9
24 18
310 15
Output
2
2