1634 - Automaton for Divisibility

Created by UCI X GrundyPC Cup
Added by ymondelo20 (2011-11-20)
Limits
Total Time: 2000 MS |Memory: 62 MB | Output: 64 MB | Size: 29 KB
Enabled languages
Available in

Description

One of the earliest computer models are finite automata, they solve many problems of computer science, computational model is a pattern recognizer languages ​​and is considered a state machine, usually a finite automaton defined as a five-tuple {Σ, Q, F, f, q0}.

Where:
Σ (the alphabet of the input string) is a set of symbols that specify which symbols make up the chains that characterize the
automaton.
Q (set of states of the automaton).
F (subset of Q) is the set of final states or acceptance, if after a string of symbols analyzed the
automaton is in a state that belongs to F, then the parsed string is considered to belong to the language that characterized the automaton.
f (transition function) domain is an ordered pair of the set Q x Σ and has as image an element of Q, its definition is the core in the process of computing the automaton. If the automaton is in the state qi and read from the input the symbol p then the automaton goes to state qk, ie f(q, p) = qk.
q0 is the initial state of the automaton, where begins the whole process of computation.

For this problem we will work with the automaton for divisibility by K (K є N), these automaton characterize the rest leaving any natural number in the division by K. After reviewing a completely natural either, the automaton is in a state q (which means that this natural leaves a remainder q on division by K). Them:

Σ = {0,1,2,3,4,5,6,7,8,9} symbols that can form any natural.
Q = {0,1,2,3,..., K-1} a state for each possible rest in division K.
F we are interested in all states therefore assume that F = Q.

q0 = 0, initial state, the rest is 0 in the division by K.
q1 = 1, remainder 1 on division by K.
q2 = 2, remainder 2 on division by K.
.
.
.
qk-1 = K-1,
remainder K-1 on division by K.

Your task is to build a computer program that since 2 <= K <= 1000, get the transition function of the automaton for divisibility by K. The transition function is represented as a matrix of K lines (states from 0 to K-1) by 10 columns (symbols). If the element in row i column j of the matrix is ​​x, then it means that being in the state i and reading input symbol j is then transits to the state x.
One of the earliest computer models are finite automata, they solve many problems of computer science, computational model is a pattern recognizer languages ​​and is considered a state machine, usually a finite automaton defined as a five-tuple {Σ, Q, F, f, q0}.

Where:
Σ (the alphabet of the input string) is a set of symbols that specify which symbols make up the chains that characterize the
automaton.
Q (set of states of the automaton).
F (subset of Q) is the set of final states or acceptance, if after a string of symbols analyzed the
automaton is in a state that belongs to F, then the parsed string is considered to belong to the language that characterized the automaton.
f (transition function) domain is an ordered pair of the set Q x Σ and has as image an element of Q, its definition is the core in the process of computing the automaton. If the automaton is in the state qi and read from the input the symbol p then the automaton goes to state qk, ie f(q, p) = qk.
q0 is the initial state of the automaton, where begins the whole process of computation.

For this problem we will work with the automaton for divisibility by K (K є N), these automaton characterize the rest leaving any natural number in the division by K. After reviewing a completely natural either, the automaton is in a state q (which means that this natural leaves a remainder q on division by K). Them:

Σ = {0,1,2,3,4,5,6,7,8,9} symbols that can form any natural.
Q = {0,1,2,3,..., K-1} a state for each possible rest in division K.
F we are interested in all states therefore assume that F = Q.

q0 = 0, initial state, the rest is 0 in the division by K.
q1 = 1, remainder 1 on division by K.
q2 = 2, remainder 2 on division by K.
.
.
.
qk-1 = K-1,
remainder K-1 on division by K.

Your task is to build a computer program that since 2 <= K <= 1000, get the transition function of the automaton for divisibility by K. The transition function is represented as a matrix of K lines (states from 0 to K-1) by 10 columns (symbols). If the element in row i column j of the matrix is ​​x, then it means that being in the state i and reading input symbol j is then transits to the state x.
One of the earliest computer models are finite automata, they solve many problems of computer science, computational model is a pattern recognizer languages ​​and is considered a state machine, usually a finite automaton defined as a five-tuple {Σ, Q, F, f, q0}.

Where:
Σ (the alphabet of the input string) is a set of symbols that specify which symbols make up the chains that characterize the
automaton.
Q (set of states of the automaton).
F (subset of Q) is the set of final states or acceptance, if after a string of symbols analyzed the
automaton is in a state that belongs to F, then the parsed string is considered to belong to the language that characterized the automaton.
f (transition function) domain is an ordered pair of the set Q x Σ and has as image an element of Q, its definition is the core in the process of computing the automaton. If the automaton is in the state qi and read from the input the symbol p then the automaton goes to state qk, ie f(q, p) = qk.
q0 is the initial state of the automaton, where begins the whole process of computation.

For this problem we will work with the automaton for divisibility by K (K є N), these automaton characterize the rest leaving any natural number in the division by K. After reviewing a completely natural either, the automaton is in a state q (which means that this natural leaves a remainder q on division by K). Them:

Σ = {0,1,2,3,4,5,6,7,8,9} symbols that can form any natural.
Q = {0,1,2,3,..., K-1} a state for each possible rest in division K.
F we are interested in all states therefore assume that F = Q.

q0 = 0, initial state, the rest is 0 in the division by K.
q1 = 1, remainder 1 on division by K.
q2 = 2, remainder 2 on division by K.
.
.
.
qk-1 = K-1,
remainder K-1 on division by K.

Your task is to build a computer program that since 2 <= K <= 1000, get the transition function of the automaton for divisibility by K. The transition function is represented as a matrix of K lines (states from 0 to K-1) by 10 columns (symbols). If the element in row i column j of the matrix is ​​x, then it means that being in the state i and reading input symbol j is then transits to the state x.

Input specification

In the first line there is the number of cases (N) to solve for this problem.
Then will follow N lines with an integer number Ki (1 <= i <= N).
In the first line there is the number of cases (N) to solve for this problem.
Then will follow N lines with an integer number Ki (1 <= i <= N).
In the first line there is the number of cases (N) to solve for this problem.
Then will follow N lines with an integer number Ki (1 <= i <= N).

Output specification

For each case you should print the matrix (which represents the transition function) with Ki rows and 10 columns.
For each case you should print the matrix (which represents the transition function) with Ki rows and 10 columns.
In the first line there is the number of cases (N) to solve for this problem.
Then will follow N lines with an integer number Ki (1 <= i <= N).

Sample input

1
2

Sample output

0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1

Hint(s)

http://coj.uci.cu/contest/
http://coj.uci.cu/contest/
http://coj.uci.cu/contest/