

Ceiling FunctionAdvanced Ceiling Manufacturers (ACM) is analyzing the properties of its new series of Incredibly CollapseProof Ceilings (ICPCs). An ICPC consists of n layers of material, each with a different value of collapse resistance (measured as a positive integer). The analysis ACM wants to run will take the collapseresistance values of the layers, store them in a binary search tree, and check whether the shape of this tree in any way correlates with the quality of the whole construction. Because, well, why should it not? To be precise, ACM takes the collapseresistance values for the layers, ordered from the top layer to the bottom layer, and inserts them onebyone into a tree. The rules for inserting a value v are:
ACM has a set of ceiling prototypes it wants to analyze by trying to collapse them. It wants to take each group of ceiling prototypes that have trees of the same shape and analyze them together. For example, assume ACM is considering five ceiling prototypes with three layers each, as described by Sample Input 1 and shown in Figure 1. Notice that the first prototype's top layer has collapseresistance value 2, the middle layer has value 7, and the bottom layer has value 1. The second prototype has layers with collapseresistance values of 3, 1, and 4 – and yet these two prototypes induce the same tree shape, so ACM will analyze them together. Given a set of prototypes, your task is to determine how many different tree shapes they induce.
Input SpecificationThe input contains several test cases. The first line of each test case contains two integers: n (1 ≤ n ≤ 50), which is the number of ceiling prototypes to analyze, and k (1 ≤ k ≤ 20), which is the number of layers in each of the prototypes. The next n lines describe the ceiling prototypes. Each of these lines contains k distinct integers (between 1 and 10^{6}, inclusive), which are the collapseresistance values of the layers in a ceiling prototype, ordered from top to bottom. Output SpecificationFor each test case, display the number of different tree shapes on a line by itself. Sample Input
Output for Sample Input


University of Debrecen; Faculty of Informatics; v. 03/01/2019 