Jinan, the central city of the southern wing of the Bohai Rim region and the lower reaches of the Yellow River in China, is the capital of Shandong Province. It is the largest city in Shandong and serves as the province's political, cultural, and educational center. It is one of the five major cities in East China, a regional financial center, and a sub-provincial city. Jinan is located in the central-western part of Shandong, bordering the Yellow River to the north and Mount Tai to the south. Jinan shares borders with Liaocheng to the southwest, Dezhou and Binzhou to the north, Zibo to the east, and Laiwu and Tai'an to the south. With a history of over 2,700 years, Jinan is the birthplace of the Longshan culture. Known as the "Spring City" due to its "Seventy-Two Famous Springs," it is celebrated for the verse: "Lotus flowers on four sides, willow trees on three; half the city is mountain scenery, half is lake." Throughout history, Jinan has been home to many literary figures, most notably Li Qingzhao and Xin Qiji. Jinan is a national innovative city, a famous software city in China, and a major national transportation hub and logistics center. Following the successful hosting of the National Games, Jinan hosted the 10th China Art Festival in 2013 and became the host city for the 22nd International Congress of Historical Sciences in 2015, injecting new vitality into Jinan's development as an international metropolis.

The Jinan "Spring History Research Group" has divided the city's springs into six regions based on their unique geological connections: Shizhong District, Lixia District, Tianqiao District, Huaiyin District, Licheng District, and Changqing District.

As a proud member of the Jinan Spring History Research Group, Mingming has collected the spring water flow indices for $N$ different years. Each index is a non-negative integer less than $2^{30}$. For the $i$-th year, the spring water flow indices for the six regions are $A(i, 1)$, $A(i, 2)$, $A(i, 3)$, $A(i, 4)$, $A(i, 5)$, and $A(i, 6)$.

Mingming now wants to know how many pairs of distinct years $(i, j)$ exist such that exactly $K$ spring regions have identical flow indices in both years.

Input

The first line contains two integers, $N$ and $K$.

Following this are $N$ lines, each containing 6 integers. The $j$-th number in the $i$-th line, $A(i, j)$, represents the spring water flow index of the $j$-th region in the $i$-th year.

Output

A single line containing one integer, representing the number of pairs of distinct years that have exactly $K$ spring regions with identical flow indices.

Examples

Input 1

3 3
1 2 3 4 5 6
1 2 3 0 0 0
0 0 0 4 5 6

Output 1

2

Subtasks

For $100\%$ of the data, $1 \leq N \leq 10^5$, $0 \leq K \leq 6$, and $K$ appears with equal probability across all data; that is, for any $0 \leq x \leq 6$, approximately $1/7$ of the test cases have $K=x$.